Генерация k-элементных подмножеств

Алгоритм генерации лексикографическом порядке:
1. выберем наименьшее в лексикографическом порядке подмножество из k элементов {0, 1, …, k-1} из имеющегося множества M= {0, 1, …, n-1}. Полученное подмножество будем хранить в {p0, p1, …, pk-1} ;
В нашем примере для n=5 и k=3 имеем {0,1,2};
2. от конца к началу текущего подмножества {p0, p1, …, pk-1} ищем первый элемент pi который можно увеличить на 1.
если такого элемента нет, мы получили последнее подмножество из k элементов {n-k, … , n-2, n-1}. В нашем примере {2,3,4} – генерация закончена;
иначе:
3. увеличиваем pi= pi +1. Всем последующим элементам pi+1, pi+2, …, pk-1 присваиваем значение большее на 1 чем предыдущий, pi+1.= pi+1;
4. выполняем пункт 2.

Задача 2. По номеру L соответствующее сочетание (подмножество). Рассмотрим решение на примере: M={0,1,2,3,4,5}, N=6 ; k=3; L=15.
Нумерация с нуля.
0) 012 4) 023 8) 035 12) 125 16) 234
1) 013 5) 024 9) 045 13) 134 17) 235
2) 014 6) 025 10) 123 14) 135 18) 245
3) 015 7) 034 11) 124 15) 145 19) 345

Генерация всех подмножеств
Задача 1. Пусть A={a0,a1,…,an-1} – множество целых чисел. Построить все его непустые подмножества.
Для построения всех подмножеств можно использовать функцию setnk(n,k):
For (k=1;k>=n;k++) setnk(n,k);
т.е. генерируем по одному, по два и т.д. до n элементов.
Битовый алгоритм. Поставим в соответствие каждому элементу множества 0 или 1. То есть каждому подмножеству соответствует n-значное число в двоичной системе счисления. Отсюда следует, что полный перебор всех подмножеств данного множества соответствует перебору всех чисел в двоичной системе счисления
от 1 до 2n – 1:
Легко подсчитать и количество различных подмножеств данного множества, оно равно 2n – 1 (или 2n, с учетом пустого множества).
Очевидно, что за 1 секунду мы можем сгенерировать множество из n ≤ 20 элементов.

#include
using namespace std;
typedef int vec[18];
vec a; int n;
void subset(vec a, int n) {
for (int mask=1;mask<1<
for(int i=0; i
if((1<
0) cout<
}
}
int main() {
cin>>n;
for(int i=0; i
subset(a, n); // n – количество элементов
return 0;
}

Размещения с повторениями
Размещения с повторениями из n по k – это последовательности длины k, в которых n возможных элементов могут повторяться.
Пример. Для n=4 и k=3, имеем:
На каждой из k позиций в последовательности независимо от других может находиться любой из n элементов, поэтому по правилу произведения общее количество размещений – nk = 43 = 64.
Задача 1. Перечислить все последовательности длины k из
чисел 0..n-1.

Алгоритм генерации размещения лексикографическом порядке
Первой будет последовательность <0,0,…,0>, печатаем. Будем хранить последнюю напечатанную последовательность в массиве x[0]..x[k-1];
2. С конца ищем элемент который можно увеличить. Так как последним является последовательность
, мы можем увеличить найденный элемент только до n-1:
если такого элемента нет, мы получили последнюю последовательность
, печатаем и заканчиваем работу;
иначе
увеличиваем его на 1, а за ним стоящие элементы приравниваем 0, печатаем;
3. повторяем пункт 2.

Размещения без повторений
Задача 1. Сгенерировать все размещения для заданного множества {0, 1, 2,…, N-1} и все размещения по K элементов в лексикографичес-ком порядке.
Пример. N = 4, K = 3.

3. С конца ищем элемент a[i] < a[i+1].
4. Если такой элемент есть, в множество свободных элементов добавляем a[i+1]. В множестве свободных элементов ищем наименьшее число большее temp = a[i]. Заменяем a[i] найденным числом и добавляем в множество свободных элементов temp. В элементы a[i+1], a[i+2],…,a[K] записываем в возрастающем порядке меньшие элементы множества свободных элементов удаляя их из этого множества. Переходим в пункт 2.
5. Если не найдено, заканчиваем поиск следующего размещения.

Рекурсивный алгоритм