Задача 98825
|
|
 |
Условие
Для заданных n и k (Решение
Будем представлять каждое подмножество последовательностью x[1]..x[n] нулей и единиц длины n, в которой ровно k единиц. (Другой способ представления разберём позже.) Такие последовательности упорядочим лексикографически (см. выше). Очевидный способ решения задачи — перебирать все последовательности как раньше, а затем отбирать среди них те, у которых k единиц — мы отбросим, считая его неэкономичным (число последовательностей с k единицами может быть много меньше числа всех последовательностей). Будем искать такой алгоритм, чтобы получение очередной последовательности требовало не более C . n действий. В каком случае s-ый член последовательности можно увеличить, не меняя предыдущие? Если x[s] меняется с 0 на 1, то для сохранения общего числа единиц нужно справа от х[s] заменить 1 на 0. Для этого надо, чтобы справа от x[s] единицы были. Если мы хотим перейти к непосредственно следующему, то x[s] должен быть первым справа нулём, за которым стоят единицы. Легко видеть, что х[s+1]=1 (иначе х[s] не первый). Таким образом надо искать наибольшее s, для которого х[s]=0, x[s+1]=1:
первая последовательность: 0..01..1
(n-k нулей, k единиц);
последняя последовательность: 1..10..0
(k единиц, n-k нулей);
алгоритм перехода к следующей за х[1]..x[n]
последовательности (предполагаем, что она есть):
s := n - 1;
while not ((x[s]=0) and (x[s+1]=1)) do begin
| s := s - 1;
end;
{s - член, подлежащий изменению с 0 на 1}
num:=0;
for k := s to n do begin
| num := num + x[k];
end;
{num - число единиц на участке x[s]...x[n], число нулей
равно (длина - число единиц), т.е. (n-s+1) - num}
x[s]:=1;
for k := s+1 to n-num+1 do begin
| x[k] := 0;
end;
{осталось поместить num-1 единиц в конце}
for k := n-num+2 to n do begin
| x[k]:=1;
end;
