Задача 98826

Тема:    [ Нерекурсивная генерация объектов ]

Сложность: 3 Классы:

Условие

Перечислить все возрастающие последовательности длины k из чисел 1..n в лексикографическом порядке. (Пример: при n=5, k=2 получаем: 12 13 14 15 23 24 25 34 35 45.)

Решение

Минимальной будет последовательность 1 2...k; максимальной — (n-k+1)...(n-1) n. В каком случае s-ый член последовательности можно увеличить? Ответ: если он меньше n-k+s. После увеличения s-го элемента все следующие должны возрастать с шагом 1. Получаем такой алгоритм перехода к следующему:

        s:=n;
        while not (x[s] < n-k+s) do begin
        | s:=s-1;
        end;
        {s - номер элемента, подлежащего увеличению};
        x[s] := x[s]+1;
        for i := s+1 to n do begin
        | x[i] := x[i-1]+1;
        end;

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	2
Название	Порождение комбинаторных объектов
параграф
Номер	3
Название	Подмножества
задача
Номер	2.3.2