Алгоритм получения перестановки, непосредственно следующей за данной

или

СkN= (N+k-1)!/(k!*(n-1)!)

Разбиения*

           Требуется подсчитать число разбиений конечного множества предметов S, где
|S|=N (количество предметов), на k различных подмножеств S=S₁ÈS₂ÈS₃È…ÈS_k, попарно не пересекающихся, |S_i|=n_i, i=1,2, …, k и n₁+n₂+…+n_k=N.

       S₁ можно сформировать  способами, S₂ -  способами ,… S_k -  способами. Таким образом, число разбиений равно , или N!/(N₁!*N₂!*…*N_k!).

1.  Алгоритм генерации всех перестановок N-элементного множества

Задача. Необходимо перечислить все перестановки для заданного значения N. Обязательное условие – отношение порядка на множестве перестановок. Предполагаем, что перестановка хранится в массиве P длины N.

       Лексикографический порядок на множестве всех перестановок определяется следующим образом: Р¹<Р² тогда и только тогда, когда существует такое t>=1, что P¹[t]<=P²[t] и P¹[i]=P²[i] для всех i<t. При решении данной задачи решается и задача получения следующей в лексикографическом порядке перестановки.

Пример (N=3).

Лексикографический

1. Имеется P= (p₁, p₂, …, p_n). Будем просматривать числа p₁, p₂, …, p_n  с конца и остановимся, когда впервые найдем p_i<p_i+1 . Если такого элемента нет, то перестановка уже имеет вид

(N, N-1, …,2,1) и является последней.

1. Итак, у нас имеется последовательность p₁<p₂… <p_i < p_i+1> p_i+2 > p_i+3…>p_n.. Будем просматривать последовательность p_i+1 > p_i+2 > p_i+3…> p_n с конца и найдем первый p_j, больший p_i и поменяем их местами. Т.е. из последовательности:

 p₁<p₂… <p_i<p_i+1> p_i+2>p_i+3…> p_j>…>p_n  получим последовательность

 p₁<p₂… <p_j<p_i+1> p_i+2>p_i+3…p_i>…>p_n.

1. Переставим элементы p_i+1> p_i+2>p_i+3…p_i>…>p_n в возрастающем порядке.

Пример. Перестановка 11,8,5,1,7,4,10,9,6,3,2. Какая следующая перестановка идет в лексикографическом порядке?

· Находим «скачок» - 4 меньше 10.

· Затем «в хвосте» перестановки находим первый элемент с конца перестановки, больший значения 4. Это значение 6.

· Меняем местами элементы 4 и 6

· «хвост» перестановки ухудшаем максимально, т.е. расставляем элементы в порядке возрастания (переворачиваем).

 Получаем перестановку 11,8,5,1,7,6,2,3,4,9,10.

1. Все K-элементные подмножества N-элементного множества (0 < K, N £ 16).
    Задан целочисленный массив A(N). Среди элементов массива нет равных (проверять массив на наличие равных элементов не нужно). Необходимо распечатать все K-элементные подмножества N-элементного множества. (N и K вводятся с клавиатуры).

Массив С(K) содержит индексы элементов массива A(N), входящих в сочетание, в лексикографическом порядке.

Пример. Перечислим все сочетания из 5-элементного множества по 3 элемента в лексикографическом порядке: 1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5, 2 3 4, 2 3 5, 2 4 5, 3 4 5.

Начальное сочетание 12..k, последнее – (N-k+1)(N-k+2)..N.

Переход от текущего сочетания к следующему осуществляется по алгоритму:

1) Просматриваем сочетание справа налево и находим первый элемент, который можно увеличить (последний k-й элемент сочетания для этого должен быть меньше или равен N, предпоследний – меньше или равен N-1 и т.д.).

2) Увеличиваем этот элемент на 1.

3) Часть сочетания (от этого элемента до конца) формируем из чисел натурального ряда, следующих за ним.

1. Все подмножества N-элементного множества (0 < N £ 16).
   Задан целочисленный массив A(N). Среди элементов массива нет равных (проверять массив на наличие равных элементов не нужно).
   Необходимо получить все подмножества данного N-элементного множества.

Способ 1. Будем перебирать K (0 < K £ 16) и находить все K- элементные подмножества N-элементного множества (см. задачу 3).

Способ 2.

Пример. Пусть определен массив char A[3] =(4, 2, 7); int N=3.

№

Двоичный код

Подмножество

Для работы с двоичным кодом числа понадобятся операции

N >> 1 – сдвиг вправо на один бит всего числа; 

N << 1 – сдвиг влево на один бит всего числа; при этом крайний левый бит вытесняется за сетку, крайний правый становится равным 0;

N & А – логическое произведение над целыми числами выполняется поразрядно над двоичным представлением числа, результат - число; например: N & 1 =1, когда в правом бите 1.

111₂=2ⁿ-1=7₁₀