Получить все последовательности длины k  из  чисел 1..n.

Решение.  Будем  печатать  их  в лексикографическом порядке (последовательность a предшествует  последовательности  b,  если для  некоторого s их начальные отрезки длины s равны, а (s+1)-ый член  последовательности  a  меньше).  Первой  будет  последовательность  <1,1,...,1>, последней - последовательность <n, n,..., n>. Будем хранить последнюю напечатанную последовательность в массиве x[1]...x[k].

        ...x[1]...x[k] положить равным 1
        ...напечатать x
        ...last[1]...last[k] положить равным n
       
while x <> last do begin
       
| ...x := следующая за x последовательность
        | ...напечатать x
        end;

Опишем, как можно перейти от x к следующей  последовательности.  Согласно определению, у следующей последовательности первые s членов должны быть такими же, а (s+1)-ый - больше.  Это возможно, если x[s+1] было меньше n. Среди таких s нужно выбрать наибольшее  (иначе полученная последовательность не будет непосредственно следующей). Соответствующее x[s+1] нужно увеличить на 1. Итак, надо, двигаясь с конца последовательности, найти  самый правый  член,  меньший  n (он найдется, так как по предположению x<>last), увеличить его на 1, а идущие  за  ним  члены  положить равными
1.

        p:=k;
        while not (x[p] < n) do begin
        | p := p-1;
        end;
        {x[p] < n, x[p+1] =...= x[k] = n}
        x[p] := x[p] + 1;
        for i := p+1 to k do begin
       
| x[i]:=1;
        end;

Замечание. Если членами последовательности считать числа не от  1 до n, а от 0 до n-1, то переход к следующему соответствует прибавлению 1 в n-ичной системе счисления.


2009-12-04 • Просмотров [ 1107 ]