Перебор всех k-элементных подмножеств

Рассмотрим задачу построения всех подмножеств данного множества, содержащих ровно k единиц. Такой объект (k-элементное подмножество n-элементного множества) можно задать несколькими способами.

Первый способ — двоичная строка длины n в которой ровно k единиц. Для построения такой строки модифицируем функцию generate, добавив в нее еще один дополнительный параметр — число единиц k, которое необходимо добавить к исходной строке. Добавляя к строке prefix символ «0», рекурсию нужно вызывать с параметрами (n−1, k), то есть нужно сгенерировать еще n−1 символ, среди которых должно быть k единиц, т. к. новых единиц добавлено не было. А если к строке prefix был добавлен символ «1», то рекурсию нужно будет вызывать с параметрами (n−1, k−1).

Но нужно поставить еще дополнительные условия, ограничивающие случаи, когда функцию можно вызывать рекурсивно. А именно, символ «1» можно добавить только в том случае, когда k>0. А символ «0» можно добавить при условии, что k<n, так как при k=n все оставшиеся символы должны быть единицами.

def generate(n, k, prefix):
if n == 0:
print(prefix)
else:
if k < n:
generate(n - 1, k, prefix + "0")
if k > 0:
generate(n - 1, k - 1, prefix + "1")

Другой способ представления множества — список выбранных элементов. Пусть в множестве nэлементов - числа от 1 до n. Тогда каждое множество - это некоторый набор из k неповторяющихся чисел от 1 до n. Чтобы представление каждого подмножества было единственным, будем считать, что числа в наборе упорядочены по возрастанию. Например, при n=4 и k=2 есть 6 различных множеств: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}.

Таким образом, задача сводится к задаче построения всех возрастающих последовательностей длины kсоставленных из чисел от 1 до n. Для построения всех таких последовательностей можно использовать следующую функцию:

def generate(n, k, prefix):
if k == 0:
print(prefix)
else:
if len(prefix) == 0:
next = 1
else:
next = prefix[-1] + 1
while next + k - 1 <= n:
generate(n, k - 1, prefix + [next])
next += 1

В этом годе параметр prefix — это список уже построенного начала последовательности, поэтому вызывать функцию generate нужно передавая последним параметром пустой список. Параметр n - это максимальное число элементов последовательности, параметр k - это количество элементов последовательности, которое еще необходимо добавить к списку prefix.

Если k=0, то больше добавлять к prefix нечего и рекурсия заканчивается. Во всех остальных случаях перебирается следующий элемент, который необходимо добавить к prefix. Его значение перебирается в цикле по переменной next. Минимальное значение next на 1 больше последнего элемента списка prefix, а если prefix пуст, то минимальное значение next равно 1. Дальше возможное значение next увеличивается на 1, при это элемент next добавляется к списку prefix. Максимальное значение next равно n−k+1, т. к. после числа next необходимо записать еще k−1 число, большее next, но не превосходящее n.

ПЕРЕБОР ВСЕХ ПЕРЕСТАНОВОК

Напишем алгоритм перебора всех перестановок чисел от 1 до n, то есть последовательности, полученной из списка чисел от 1 до n изменением порядка их следования. Известно, что таких перестановок существует n!, напишем функцию, которая выводит все перестановки в лексикографическом порядке.

Как и ранее, функция получает в качестве параметра значение n (длина перестановки) и prefix - уже построенное начало перестановки. Далее перебираются все числа от 1 до n в порядке возрастания в качестве возможного продолжения перестановки. Если число не содержится в списке prefix, то к списку prefix добавляется следующий элемент последовательности и функция вызывается рекурсивно.

Окончание рекурсии происходит в случае, если список prefix имеет длину n, то есть все числа от 1 до nуже содержатся в списке prefix.

def generate(n, prefix):
if len(prefix) == n:
print(prefix)
else:
for next in range(1, n + 1):
if next not in prefix:
generate(n, prefix + [next])