Алгоритм 1.19 (ст. 51-52), Алгоритм 1.22 (ст. 57-58) за посібником «Комбінаторика для програмістів» (Липський В.)

Алгоритм 1.19. (Генерирование всех разбиений множества {1, 2,...,n}). Данные: n. Результат: Последовательность всех разбиений множества {1,...,n}, в которой каждое следующее разбиение образуется из предыдущего путем перенесения единственного элемента в другой блок.

1. begin
2. for i := 1 to n do (*поместить i в первый блок*)
3. begin БЛОК[i] := 1; ВПЕР[i]:= истина;
4. end;
5. СЛЕД[1] := 0;
6. выписать разбиение;
7. j := n; (*j=активный элемент*)
8. while j > 1 do
9. begin k := БЛОК[j];
10. if ВПЕР[j] then (*j движется вперед*)
11. begin
12. if СЛЕД[k]=0 then (*k естьпоследний блок*)
13. begin СЛЕД[k] := j; ПРЕД[j] := k; СЛЕД[j] := 0
14. end;
15. if СЛЕД[k] > j then (*j образует новый блок*)
16. begin ПРЕД[j] := k; СЛЕД[j] := СЛЕД[k];
17. ПРЕД[СЛЕД[j]] := j; СЛЕД[k] := j
18. end;
19. БЛОК[j] := СЛЕД[k]
20. end
21. else (*j движется назад*)
22. begin БЛОК[j] := ПРЕД[k];
23. if k = j then (*j образует одноэлементный блок*)
24. if СЛЕД[k]=0 then СЛЕД[ПРЕД[k]] := 0
25. else begin СЛЕД[ПРЕД[k]] := СЛЕД[k];
26. ПРЕД[СЛЕД[k]] := ПРЕД[k]
27. end
28. end;
29. выписать разбиение;
30. j := n;
31. while (j > 1) and
32. ((ВПЕР[j] and (БЛОК[j] = j)) or (not ВПЕР[j] and (БЛОК[j]=1))) do
33. begin ВПЕР[j]:=not ВПЕР[j]; j := j − 1;
34. end
35. end
36. end

Алгоритм 1.22. (Нахождение всех разбиений числа) Данные: n. Результат: последовательность разбиений числа n в порядке, обратном лексикографическому.

1. begin
2. S[1] := n; R[1] := 1; n := 1; (*первое разбиение*)
3. выписать разбиение;
4. while S[1] > 1 do (*нахождение следующего разбиения*)
5. begin sum := 0; (*sum = сумма устраненных слагаемых*)
6. if S[d]=1 then (*удаление слагаемых, равных единице*)
7. begin sum := sum + R[d]; d := d − 1
8. end;
9. sum := sum + S[d]; R[d] := R[d] − 1; l := S[d] − 1;
10. if R[d] > 0 then d := d + 1;
11. S[d] := l; R[d]:=sum div l;
12. l:=sum mod l;
13. if l >= 0 then (*добавить последнее слагаемое, равное l*)
14. begin d := d + l; S[d] := l; R[d] := 1
15. end;
16. выписать разбиение
17. end
18. end