Помогите решить  на С#
    №1.
 Напечатать все последовательности длины k  из  чисел
1..n.

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

      
     Опишем, как можно  перейти  от  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-ичной системе счисления.
 №2. 
Напечатать все подмножества множества {1...k}.

     Решение.  Подмножества находятся во взаимно однозначном со-
ответствии с последовательностями нулей и единиц длины k.
№3.
 Напечатать все перестановки чисел 1..n (то есть пос-
ледовательности  длины  n, в которые каждое из чисел 1..n входит
по одному разу).

     Решение. Перестановки будем  хранить  в  массиве  x[1],...,
x[n]  и  печатать в лексикографическом порядке. (Первой при этом
будет перестановка <1 2...n>, последней - <n...2 1>.)  Для  сос-
тавления  алгоритма  перехода к следующей перестановке зададимся
вопросом: в каком случае k-ый член перестановки можно увеличить,
не меняя предыдущих? Ответ: если он меньше какого-либо из следу-
ющих членов (членов с номерами больше k). Мы  должны  найти  на-
ибольшее  k,  при  котором  это  так,  т. е. такое k, что x[k] <
x[k+1] > ... > x[n]. После  этого  x[k]  нужно  увеличить  мини-
мальным  возможным способом, т. е. найти среди x[k+1], ..., x[n]
наименьшее число, большее его. Поменяв x[k] с ним, остается рас-
положить числа с номерами k+1, ..., n  так,  чтобы  перестановка
была наименьшей, то есть в возрастающем порядке. Это облегчается
тем, что они уже расположены в убывающем порядке.

     Алгоритм перехода к следующей перестановке.

 
   ... переставить участок x[k+1] ... x[n] в обратном порядке

Замечание. Программа имеет знакомый  дефект:  если  t  =  n,  то
x[t+1] не определено.

     №4.
 Перечислить все k-элементные подмножества  множества
{1..n}.

     Решение.  Будем представлять каждое подмножество последова-
тельностью x[1]..x[n] нулей и единиц длины n, в которой ровно  k
единиц. (Другой способ представления разберем позже.) Такие пос-
ледовательности упорядочим лексикографически (см. выше). Очевид-
ный  способ  решения  задачи - перебирать все последовательности
как раньше, а затем отбирать среди них те, у которых k единиц  -
мы отбросим, считая его неэкономичным (число последовательностей
с  k  единицами  может  быть  много меньше числа всех последова-
тельностей). Будем искать такой алгоритм, чтобы  получение  оче-
редной последовательности требовало порядка n действий.
     В каком случае s-ый член  последовательности  можно  увели-
чить,  не  меняя предыдущие? Если x[s] меняется с 0 на 1, то для
сохранения общего числа единиц нужно справа от х[s]  заменить  1
на 0. Таким образом, х[s] - первый справа нуль, за которым стоят
единицы.  Легко  видеть,  что х[s+1] = 1 (иначе х[s] не первый).
Таким образом надо искать наибольшее  s,  для  которого  х[s]=0,
x[s+1]=1;

                  ______________________
               x |________|0|1...1|0...0|
                           s

За х[s+1] могут идти еще несколько единиц, а после них несколько
нулей. Заменив х[s] на 1, надо выбрать идущие за ним члены  так,
чтобы последовательность была бы минимальна с точки зрения наше-
го  порядка,  т. е. чтобы сначала шли нули, а потом единицы. Вот
что получается:

  первая последовательность    0...01...1 (n-k нулей, k единиц)
  последняя последовательность 1...10...0 (k единиц, n-k нулей)

  алгоритм перехода к следующей за х[1]...x[n] последовательнос-
  ти (предполагаем, что она есть):

     

     Другой  способ представления подмножеств - это перечисление
их  элементов.  Чтобы  каждое  подмножество  имело  ровно   одно
представление,  договоримся  перечислять элементы в возрастающем
порядке. Приходим к такой задаче.
 №5.
 Перечислить все возрастающие последовательности дли-
ны  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. Получаем такой алгоритм перехода к следующему:

       
№6. 
Перечислить все разбиения целого положительного чис-
ла  n  на целые положительные слагаемые (разбиения, отличающиеся
лишь порядком слагаемых, считаются за одно). (Пример: n=4,  раз-
биения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)

     Решение. Договоримся, что (1) в разбиениях слагаемые идут в
невозрастающем порядке, (2) сами разбиения мы перечисляем в лек-
сикографическом  порядке.  Разбиение  храним  в  начале  массива
x[1]...x[n], при этом количество входящих в него чисел обозначим
k. В начале x[1]=...=x[n]=1, k=n, в конце x[1]=n, k=1.
     В  каком  случае  x[s] можно увеличить не меняя предыдущих?
Во-первых, должно быть x[s-1] > x[s] или s  =  1.  Во-вторых,  s
должно  быть не последним элементом (увеличение s надо компенси-
ровать уменьшением следующих). Увеличив s, все следующие элемен-
ты надо взять минимально возможными.

      

M Rodman

Модератор: Пожалуйста, один топик - один вопрос.