Сочетания
Сочетанием из n по k называют подмножество n-элементного множества, содержащее ровно k элементов. Например, если в качестве множества рассматривать натуральные числа от 1 до 5, то сочетания из 5 по 4 – это 4-элементные подмножества множества {1,2,3,4,5}:
{2, 3, 4, 5}, {1, 3, 4, 5}, {1, 2, 3, 5}, {1, 2, 3, 4}.
Количество сочетаний из n по k обозначают через Cnk и называют биномиальными коэффициентами. Их вычисление подробно обсуждается в главе "Динамическое программирование". Обсудим задачу перечисления всех сочетаний. Конечно, можно перебирать все подмножества, и выбирать их них те, которые имеют нужную длину, но это может потребовать слишком много времени. Например, если n=1000, а k=2, то количесто подмножеств равно 21000, а количество сочетаний из 1000 по 2 – всего 1000 * 999 / 2.
Будем представлять сочетание возрастающей последовательностью его элементов. Например, сочетание {1, 5, 3, 2} будем представлять как последовательность 1, 2, 3, 5. Для таких последовательностей можно ввести естественный лексикографический порядок, например, для последовательностей, соответствующих сочетаниям из 4 по 3:
1, 2, 3 → 1, 2, 4 → 1, 3, 4 → 2, 3, 4.
Сформулируем правило, по которому мы можем получить из некоторого сочетания следующее за ним в лексикографическом порядке. Рассмотрим, например, такое сочетание по 6 элементов из 9: 1, 3, 4, 7, 8, 9. Найдем самую правую цифру, которую мы можем увеличить, не меняя цифр левее ее – это цифра 4. Увеличим ее на 1 – следующее сочетание будет начинаться с 1, 3, 5. Какие числа нужно поставить после 5, чтобы получить наименьшее сочетание с таким началом? Это минимальные числа, большие 5, причем их следует записать в возрастающем порядке: 6, 7, 8. Таким образом, получится сочетание 1, 3, 5, 6, 7, 8.
Как мы нашли самую правую цифру, которую можно увеличить? Последняя цифра равна 9 (n), поэтому ее увеличить нельзя, следующая цифра, равна 8 (n–1), но на этом месте в возрастающей последовательности б'ольшую цифру поставить нельзя и т. д. В общем случае, на i-м месте справа не может стоять число, большее (n–i+1). Таким образом, мы ищем минимальное i (i ≥ 1), такое что на i-м месте справа стоит число, меньшее (n–i+1). Это число мы увеличиваем на 1, а следом за ним записываем числа, большие его на 1, 2, 3 и т. д.
Напишем код соответствующей функции (функция будет возвращать false, если данное сочетание является последним). Текущее сочетание будем хранить в массиве a.
function Next : boolean;
begin
i:=1;
while (i<=k) AND (a[k-i+1]=n-i+1) do //ищем число, которое увеличим
Inc(i);
if i<=k then begin
Inc(a[k-i+1]); //увеличиваем число
for j:=k-i+2 to k do
a[j]:=a[j-1]+1; //изменяем следующие числа
Next := true;
end
else
Next := false; //сочетание было последним
end;
В основной программе мы должны записать в массив a первое сочетание, и затем вызывать функцию Next до тех пор, пока она возвращает true. Процедура Print печатает текущее сочетание.
begin
read(n, k);
for l:=1 to k do
a[l]:=i;
Print;
while Next do
Print;
end.
Данную программу можно еще ускорить, воспользовавшись следующим наблюдением. Пусть мы нашли самый правый элемент a[s] = x, который можно увеличить. Как определить, какой элемент мы должны увеличить при генерации следующего сочетания? На данном шаге мы получим сочетание, на конце которого стоят числа x+1, x+2, …, x+t. Если мы можем увеличить на следующем шаге последнее число. то его и нужно увеличивать. Если же оно максимально, то и все перечисленные выше числа также максимальны, а первым кандидатом на увеличение будет число a[s–1]. Может ли так оказаться, что его нельзя увеличить? Оказывается, нет. Действительно, если a[s] было равно x, и мы смогли его увеличить, то a[s – 1] ≤ x – 1, и его также можно увеличить. Таким образом, на следующем шаге мы будем увеличивать либо последний элемент, если он меньше n, либо элемент, предшествующий тому, который мы увеличили на данном шаге.
Таким образом, фрагмент для выбора элемента можно переписать, заменив старый код
i:=1;
while (i<=k) AND (a[k-i+1]=n-i+1) do
Inc(i);
на такой:
if a[k]<n then
i:=1
else
i:=i+1;
В основной программе зададим начальное значение i. Оно играет роль, если a[k] = n, то есть если k = n. В этом случае существует всего одно сочетание, и больше ничего искать не нужно, поэтому можно положить i := k. Тогда в первый раз оно увеличиться до k + 1 и функция Next закончит свою работу со значением FALSE.
