Генерация выборки из n по m, следующей за данной

Функция находит выборку, следующую за данной в лексикографическом порядке. Начальная выборка задается в массиве X, туда же после работы функции помещается найденная выборка. Результат функции равен истине, если на вход подана выборка являющаяся последней при лексикографическом упорядочивании. Таким образом чтобы получить все выборки - надо инициализировать массив X значениями 1, 2, ..., m и последовательно вызывать функцию до тех пор пока результат не окажется равным истине. Числа внутри выборки, поданной на вход функции, должны быть упорядочены по возрастанию.

Заметим, что количество выборок m из n равно числу сочетаний m из n и вычисляется с помощью этого алгоритма.

Если нашли ошибку в алгоритме - сообщите!

Реализации алгоритма на различных языках:

Блоксхемы:

Реализация алгоритма на AlgoPascal:

unit RetrievalUnit;

interface
    NextRetrieval;
implementation

(*
Выборки из n элементов по m.

function NextRetrieval(n,m:integer; var x:array[1..m] of integer):Boolean;

процедура находит выборку следующую в лексикографическом порядке
за выборкой заданной в массиве X. Если выборка в массиве последняя,
то переменной Result присваивается значение True, иначе False.
*)
function NextRetrieval(
    const   n   :   Integer;
    const   m   :   Integer;
    var     x   :   array of Integer):Boolean;
var
    I   :   Integer;
begin
    Result:=False;
    i:=m;
    while i>0 do
    begin
        if x[i]<n-(m-i) then
            Break;
        i:=i-1;
    end;
    
    if i>0 then
    begin
        x[i]:=x[i]+1;
        i:=i+1;
        while i<=m do
        begin
            x[i]:=x[i-1]+1;
            i:=i+1
        end;
    end
    else
    begin
        Result:=True;
    end;
end;

end.

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU