Algoritmus Tompkins – Paige - Tompkins–Paige algorithm

The Algoritmus Tompkins – Paige^[1] je počítač algoritmus pro generování všech obměny konečné sady objektů.

Metoda

Nechat P a C být pole délky n s 1 indexování (tj. první položka pole má index 1). Algoritmus pro generování všech n! permutace množiny {1, 2, ..., n} je dán následujícím pseudo kód:

P ← [1, 2, ..., n]; výtěžek P;C ← [*, 1, ..., 1]; (první záznam z C není používán)i ← 2;zatímco i ≤ n dělat    otočit doleva první i záznamy z P; (např. otáčení vlevo první 4 položky [4, 2, 5, 3, 1] dá [2, 5, 3, 4, 1]) -li C[i] < i pak        C[i] ← C[i] + 1;        i ← 2; výtěžek P;    jiný        C[i] ← 1;        i ← i+1;

Ve výše uvedeném pseudokódu je výrok „výnos P"znamená vydávat nebo zaznamenávat sadu permutovaných indexů P. Pokud je algoritmus implementován správně, P budou získány přesně n! krát, každý s jinou sadou permutovaných indexů.

Tento algoritmus není nejúčinnější ze všech existujících metod generování permutace.^[2] Musí nejen sledovat pomocné počítací pole (C), jsou také vytvářeny a ignorovány nadbytečné obměny (protože P není získáno po otočení doleva, pokud C[i] ≥ i) v průběhu generace. Například kdy n = 4, algoritmus nejprve získá P = [1,2,3,4] a poté vygenerujte dalších 23 permutací ve 40 iteracích (tj. V 17 iteracích jsou redundantní permutace a P není poskytnuta). Následující seznamy, v pořadí generování, všech 41 hodnot P, Kde v závorkách ty jsou nadbytečné:

P = 1234 c = * 111 i = 2P = 2134 c = * 211 i = 2P = (1234) c = * 111 i = 3P = 2314 c = * 121 i = 2P = 3214 c = * 221 i = 2P = ( 2314) c = * 121 i = 3P = 3124 c = * 131 i = 2P = 1324 c = * 231 i = 2P = (3124) c = * 131 i = 3P = (1234) c = * 111 i = 4P = 2341 c = * 112 i = 2P = 3241 c = * 212 i = 2P = (2341) c = * 112 i = 3P = 3421 c = * 122 i = 2P = 4321 c = * 222 i = 2P = (3421) c = * 122 i = 3P = 4231 c = * 132 i = 2P = 2431 c = * 232 i = 2P = (4231) c = * 132 i = 3P = (2341) c = * 112 i = 4P = 3412 c = * 113 i = 2P = 4312 c = * 213 i = 2P = (3412) c = * 113 i = 3P = 4132 c = * 123 i = 2P = 1432 c = * 223 i = 2P = (4132) c = * 123 i = 3P = 1342 c = * 133 i = 2P = 3142 c = * 233 i = 2P = (1342) c = * 133 i = 3P = (3412) c = * 113 i = 4P = 4123 c = * 114 i = 2P = 1423 c = * 214 i = 2P = (4123) c = * 114 i = 3P = 1243 c = * 124 i = 2P = 2143 c = * 224 i = 2P = (1243) c = * 124 i = 3P = 2413 c = * 134 i = 2P = 4213 c = * 234 i = 2P = (2413) c = * 134 i = 3P = (4123) c = * 114 i = 4P = (1234) c = * 111 i = 5

Reference