); writeln end
else
begin
for j: = i +1 to n do
begin
Perm (i +1);
k: = p [i]; p [i]: = p [j]; p [j]: = k
end;
Perm (i +1);
{циклічний зсув елементів i .. n вліво}
k: = p [i];
for j: = i to n-1 do p [j]: = p [j +1];
p [n]: = k
end
end; {Perm}
begin {Permutations}
Perm (1)
end;
begin {Main}
readln (n);
for i: = 1 to n do p [i]: = i;
a : = p ; {масив a може бути заповнений довільно}
Permutations (n)
end.
Зауважимо, що в даній програмі масив p можна було і не використовувати, а переставляти безпосередньо елементи масиву a.
В
Розбивки безлічі
Число розбиттів n -елементного безлічі на k блоків довільного розміру, але таких, що кожен елемент безлічі виявляється "приписаний" до одного з блоків, виражається числом Стірлінга другого роду S ( n , k ) [6,7]. Очевидно, що S ( n , k ) = 0 для k > n . Якщо погодитися, що існує тільки один спосіб розбиття порожнього множини на нульове число непорожніх частин, те S (0,0) = 1 (саме така домовленість, як і у випадку з факторіалом, приводить надалі до універсальним формулами). Так як при розбитті непорожньої безлічі потрібна, по Принаймні, одна частина, S ( n , 0) = 0 при n > 0. Окремо цікаво також розглянути випадок k = 2. Якщо непорожнє безліч розділили на дві непорожні частини, то в першій частині може виявитися будь-яка підмножина вихідного безлічі, за винятком підмножин, що включають в себе останній елемент безлічі, а що залишилися елементи автоматично потрапляють в другу частину. Такі підмножини можна вибрати 2 n -1 - 1 способами, що і відповідає S ( n , 2) при n > 0. p> Для довільного k можна міркувати так. Останній елемент або буде представляти із себе окремий блок в розбитті і тоді залишилися елементи можна розбити вже на k - 1 частин S ( n - 1, k - 1) способами, або поміщаємо його в непорожній блок. В останньому випадку мається kS ( n - 1, k ) можливих варіантів, оскільки останній елемент ми можемо додавати в кожен блок розбиття перших n - 1 елементів на k частин. Таким чином
S ( n , k ) = S ( n - 1, k - 1) + kS ( n - 1, k ), n > 0. (5)
Корисними можуть виявитися також формули, що зв'язують числа Стірлінга з біноміальними коефіцієнтами, визначальними число сполучень:
В
br/>
Якщо ж значення k тепер не фіксувати і розглянути всі розбиття n -елементного множини, то їх кількість виражається числом Белла
В
За формулами (7) можна підрахувати, що в рамках прийнятих вище припущень можна побудувати всі розбиття множини, складається не більше ніж з 15 елементів ( B 15 = 1382958545).
Перейдемо тепер до розгляду способу генерації всіх розбиттів вихідного безлічі. Перш за все, слід домовитися про те, як позначати поточне розбиття. Так як в кожному з разбиений беруть участь всі елементи вихідної безлічі, будемо в масиві індексів p записувати в який блок потрапляє кожен з елементів у поточному розбитті. Параметр i в рекурсивної процедурою part означає, що на поточному кроці ми саме i-ий елемент буде розміщувати в кожному з допустимих для нього блоків, а j як раз і визначає максимальний номер допустимого блоку. Після того, як i-ий елемент поміщений в один з блоків, рекурсивно вирішується таке ж завдання вже для наступного елементу (у даному випадку фактично працює універсальна схема перебору з поверненням [8]).
procedure partition (n: integer; var p: list);
procedure part (i, j: integer);
var l: integer;
begin
if i> n then print (n, p) else
for l: = 1 to j do
begin
p [i] : = L;
if l = j then part (i +1, j +1)
else part (i +1, j)
end
end; {Part}
begin { partition }
part (1,1)
end ;
Як не дивно, в даному випадку процедура print виявляється зовсім не тривіальною, якщо потрібно друкувати (або аналізувати) елем...
