Як перебрати всі перестановки і про факториальном розкладання натуральних чисел

Задачі про переборі всіх можливих перестановок заданого безлічі сутностей виникають у програмуванні досить часто. Як відомо з комбінаторики, число можливих перестановок n предметів одно просто факториалу числа n

n! = n * (n — 1) * (n– 2) *… * 3 * 2 * 1

Факторіал – досить швидко зростаюча функція, про це говорить її асимптотика (формула Стірлінга), хоча досить подивитися на факториалы декількох перших членів натурального ряду:

1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
11! 39 916 800
12! 479 001 600
13! 6 227 020 800
14! 87 178 291 200
15! 1 307 674 368 000

Як видно, факторіал 13-ти вже не вміщується в тип даних long.

Якщо задатися метою знайти однозначну відповідність між номером перестановки — числом в діапазоні від 1 до n! – і її реалізацією, можна натрапити на один дуже цікавий математичний факт.

Для початку згадаємо поняття позиційної системи числення. Внесок кожного розряду числа його значення в позиційній системі з основою K є розряд, помножений на підставу K в ступені, що дорівнює позиції розряду в записі числа. Основа системи числення зазвичай пишуть як підрядковий індекс, таким чином

196610 = 1*103 + 9 * 102 + 6 * 101 + 6 (*100)

101100012 = 1 * 27 + 0 * 26 + 1 * 25 + 1 * 24 + 0 * 23 + 0 * 22 + 0 * 21 + 1 * 20 (=17710)

Позиційна запис, крім компактності, володіє тим безцінним властивістю, що алгоритм виконання арифметичних операцій виявляється надзвичайно простим (є історична байка, що в школах середньовіччя вивчення арифметики займало кілька років, оскільки обчислення над числами в НЕпозиционной римської запису мали безліч правил для того, щоб провести просте додавання!)

Виявляється, існує, і є однозначним розкладання і спосіб запису числа, в якому кожен розряд в такому його уявленні множиться на ФАКТОРІАЛ номера позиції.

Покажемо це на прикладах:

1985 = 2 * 6! + 4 * 5! + 0 * 4! + 2 * 3! + 2 * 2! + 1 * 1!

2 940 861 129 405 = 2*15! + 3*14! + 10*13! + 3*12! + 6*11! + 8*10! + 4*9! + 8*8! + 0*7! + 2*6! + 2*5! + 1*4! + 3*3! + 1*2! + 1*1!

У звичайній позиційній системі значення кожного розряду має бути строго менше підстави. У факторіальною же системі кожен «розряд» менше або дорівнює основи факторіала, перед якою він стоїть. При цьому діють звичайні для складання правила переносу розряду при переповненні.

Більш математично строго: кожне натуральне число n можна єдиним чином представити у вигляді наступної суми

де
km <= m – коефіцієнт при m! — він же розряд числа його факториальном поданні,
p – кількість розрядів в числі його факториальном поданні
тобто число записується як kp kp-1 kp-2… k2 k1

Тепер опишемо, як використовувати факториальное подання (розкладання) числа для генерації відповідної перестановки. Розташуємо n елементів у порядку зростання індексу від 1 до n. Для кожного числа в діапазоні 0..n!-1 зробимо факториальное розкладання, обчисливши його коефіцієнти km. В розкладанні нуля коефіцієнти km будуть всі нулі, в розкладанні числа n!-1 все km = m, m змінюється в діапазоні від 0 до n-1. Тепер помістимо елемент з номером m на місце з номером km+1, рахуючи лише вільні місця, що залишились до цього кроку. Фактично, ця процедура повторює міркування, які наводяться при обчисленні числа можливих перестановок з n елементів – перший елемент може бути розміщений n способами, другий – (n-1) способом і так далі. Таким чином, ми отримаємо всі можливі перестановки з n незбіжних елементів.

Проілюструємо це для 5 предметів (120 варіантів перестановок) і перестановки №77
77 = 3 * 4! + 0 * 3! + 2 * 2! + 1 * 1!



Не будучи програмістом-практиком, я все ж висловлю припущення (теоретичні)), як можна було б використовувати подібне розкладання. Можна розбити загальне число можливих перестановок на піддіапазони за кількістю наявних паралельних потоків виконання, і отримувати поточну перестановку прямо з представлення змінної циклу в факторіальною запису. Розкладання в факториальную форму – завдання досить обчислювально складна, але можна розкласти тільки стартове число піддіапазону, а потім просто додавати одиницю, переносячи її в наступний розряд у разі переповнення.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.