Генерация сочетаний из N элементов

Сочетания из N элементов по K в лексикографическом порядке

Постановка задачи. Даны натуральные числа N и K. Рассмотрим множество чисел от 1 до N. Требуется вывести все различные его подмножества мощности K, причём в лексикографическом порядке.

Алгоритм весьма прост. Первым сочетанием, очевидно, будет сочетание (1,2,...,K). Научимся для текущего сочетания находить лексикографически следующее. Для этого в текущем сочетании найдём самый правый элемент, не достигший ещё своего наибольшего значения; тогда увеличим его на единицу, а всем последующим элементам присвоим наименьшие значения.

bool next_combination (vector<int> & a, int n) {
	int k = (int)a.size();
	for (int i=k-1; i>=0; --i)
		if (a[i] < n-k+i+1) {
			++a[i];
			for (int j=i+1; j<k; ++j)
				a[j] = a[j-1]+1;
			return true;
		}
	return false;
}

С точки зрения производительности, этот алгоритм линеен (в среднем), если K не близко к N (т.е. если не выполняется, что K = N - o(N)). Для этого достаточно доказать, что сравнения "a[i] < n-k+i+1" выполняются в сумме C_n+1^k раз, т.е. в (N+1) / (N-K+1) раз больше, чем всего есть сочетаний из N элементов по K.

Сочетания из N элементов по K с изменениями ровно одного элемента

Требуется выписать все сочетания из N элементов по K, но в таком порядке, что любые два соседних сочетания будут отличаться ровно одним элементом.

Интуитивно можно сразу заметить, что эта задача похожа на задачу генерации всех подмножеств данного множества в таком порядке, когда два соседних подмножества отличаются ровно одним элементом. Эта задача непосредственно решается с помощью Кода Грея: если мы каждому подмножеству поставим в соответствие битовую маску, то, генерируя с помощью кодов Грея эти битовые маски, мы и получим ответ.

Может показаться удивительным, но задача генерации сочетаний также непосредственно решается с помощью кода Грея. А именно, сгенерируем коды Грея для чисел от 0 до 2^N-1, и оставим только те коды, которые содержат ровно K единиц. Удивительный факт заключается в том, что в полученной последовательности любые две соседние маски (а также первая и последняя маски) будут отличаться ровно двумя битами, что нам как раз и требуется.

Докажем это.

Для доказательства вспомним факт, что последовательность G(N) кодов Грея можно получить следующим образом:

G(N) = 0G(N-1) ∪ 1G(N-1)^R

т.е. берём последовательность кодов Грея для N-1, дописываем в начало каждой маски 0, добавляем к ответу; затем снова берём последовательность кодов Грея для N-1, инвертируем её, дописываем в начало каждой маски 1 и добавляем к ответу.

Теперь мы можем произвести доказательство.

Сначала докажем, что первая и последняя маски будут отличаться ровно в двух битах. Для этого достаточно заметить, что первая маска будет иметь вид N-K нулей и K единиц, а последняя маска будет иметь вид: единица, потом N-K-1 нулей, потом K-1 единица. Доказать это легко по индукции по N, пользуясь приведённой выше формулой для последовательности кодов Грея.

Теперь докажем, что любые два соседних кода будут отличаться ровно в двух битах. Для этого снова обратимся к формуле для последовательности кодов Грея. Пусть внутри каждой из половинок (образованных из G(N-1)) утверждение верно, докажем, что оно верно для всей последовательности. Для этого достаточно доказать, что оно верно в месте "склеивания" двух половинок G(N-1), а это легко показать, основываясь на том, что мы знаем первый и последний элементы этих половинок.

Приведём теперь наивную реализацию, работающую за 2^N:

int gray_code (int n) {
	return n ^ (n >> 1);
}

int count_bits (int n) {
	int res = 0;
	for (; n; n>>=1)
		res += n & 1;
	return res;
}

void all_combinations (int n, int k) {
	for (int i=0; i<(1<<n); ++i) {
		int cur = gray_code (i);
		if (count_bits (cur) == k) {
			for (int j=0; j<n; ++j)
				if (cur & (1<<j))
					printf ("%d ", j+1);
			puts ("");
		}
	}
}

Стоит заметить, что возможна и в некотором смысле более эффективная реализация, которая будет строить всевозможные сочетания на ходу, и тем самым работать за O (C_n^k n). С другой стороны, эта реализация представляет собой рекурсивную функцию, и поэтому для небольших n, вероятно, она имеет большую скрытую константу, чем предыдущее решение.

Собственно сама реализация - это непосредственное следование формуле:

G(N,K) = 0G(N-1,K) ∪ 1G(N-1,K-1)^R

Эта формула легко получается из приведённой выше формулы для последовательности Грея - мы просто выбираем подпоследовательность из подходящих нам элементов.

bool ans[MAXN];

void gen (int n, int k, int l, int r, bool rev, int old_n) {
	if (k > n || k < 0)  return;
	if (!n) {
		for (int i=0; i<old_n; ++i)
			printf ("%d", (int)ans[i]);
		puts ("");
		return;
	}
	ans[rev?r:l] = false;
	gen (n-1, k, !rev?l+1:l, !rev?r:r-1, rev, old_n);
	ans[rev?r:l] = true;
	gen (n-1, k-1, !rev?l+1:l, !rev?r:r-1, !rev, old_n);
}

void all_combinations (int n, int k) {
	gen (n, k, 0, n-1, false, n);
}