Томпкинс - Пейдж алгоритмі - Tompkins–Paige algorithm

The Томпкинс - Пейдж алгоритмі^[1] Бұл компьютер алгоритм бәрін жасау үшін ауыстыру объектілердің ақырғы жиынтығы.

Әдіс

Келіңіздер P және в массивтер болуы керек n 1 негізделген индекстеу (яғни массивтің бірінші жазбасында 1 индексі бар). Барлығын генерациялау алгоритмі n! {1, 2, ..., жиынының орын ауыстырулары n} келесі түрде беріледі псевдокод:

P ← [1, 2, ..., n]; кірістілік P;в ← [*, 1, ..., 1]; (бірінші жазба в қолданылмайды)мен ← 2;уақыт мен ≤ n істеу    біріншісін солға бұру мен жазбалары P; (мысалы, [4, 2, 5, 3, 1] алғашқы 4 жазбаны солға айналдыру [2, 5, 3, 4, 1] береді) егер в[мен] < мен содан кейін        в[мен] ← в[мен] + 1;        мен ← 2; Өткізіп жібер P;    басқа        в[мен] ← 1;        мен ← мен+1;

Жоғарыдағы жалған кодта «кірістілік P«рұқсат етілген индекстер жиынтығын шығаруды немесе жазуды білдіреді P. Егер алгоритм дұрыс орындалса, P дәл берілетін болады n! рет, әрқайсысы әртүрлі индекстер жиынтығымен.

Бұл алгоритм барлық қолданыстағы ауыстырудың генерациялау әдістерінің ішіндегі ең тиімдісі емес.^[2] Ол көмекші санау массивін қадағалап қана қоймай (в), артық ауыстырулар да шығарылады және еленбейді (өйткені P солға айналғаннан кейін берілмейді, егер в[мен] ≥ мен) буын барысында. Мысалы, қашан n = 4, алгоритм алдымен нәтиже береді P = [1,2,3,4], содан кейін басқа 23 орын ауыстыруды 40 қайталануда жасаңыз (яғни 17 қайталануда артық ауысулар болады және P берілмейді). Келесі тізбектер генерация реті бойынша барлық 41 мәндерін береді P, қайда жақша ішінде біреуі артық:

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

Пайдаланылған әдебиеттер