Комбинаторика и переборные на С# - C#

Формулировка задачи:

Помогите решить эти задачи на C# :

№1.

Напечатать все последовательности длины 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-ичной системе счисления.

№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[1],...,x[n-1], x[n]> <> <n,...,2, 1>.}
  k:=n-1;
  {последовательность справа от k убывающая: x[k+1] >...> x[n]}
  while x[k] > x[k+1] do begin
  | k:=k-1;
  end;
  {x[k] < x[k+1] > ... > x[n]}
  t:=k+1;
  {t <=n, x[k+1] > ... > x[t] > x[k]}
   while (t < n) and (x[t+1] > x[k]) do begin
   | t:=t+1;
   end;
   {x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]}
   ... обменять x[k] и x[t]
   {x[k+1] > ... > x[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] последовательнос- ти (предполагаем, что она есть):

 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;
        for k := n-num+2 to n do begin
        | x[k]:=1;
        end;

Другой способ представления подмножеств - это перечисление их элементов. Чтобы каждое подмножество имело ровно одно представление, договоримся перечислять элементы в возрастающем порядке. Приходим к такой задаче.

№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. Получаем такой алгоритм перехода к следующему:

 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;

№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, все следующие элемен- ты надо взять минимально возможными.

s := k - 1;
        while not ((s=1) or (x[s-1] > x[s])) do begin
        | s := s-1;
        end;
        {s - подлежащее увеличению слагаемое}
        x [s] := x[s] + 1;
        sum := 0;
        for i := s+1 to k do begin
        | sum := sum + x[i];
        end;
        {sum - сумма членов, стоявших после x[s]}
        for i := 1 to sum-1 do begin
        | x [s+i] := 1;
        end;
        k := s+sum-1;

Решение задачи: «Комбинаторика и переборные на С#»

textual
                            Листинг программы 
                        

                              Console.WriteLine("Ввести значение k=");
            int k = int.Parse(Console.ReadLine());
            Console.WriteLine("Ввести значение n=");
            int n = int.Parse(Console.ReadLine());
            int[] x = new int[n-1];
            int[] x1 = new int[k - 1];
            int i,j,s=0;
            int p=0;
            for (int y = 0; y <= k;y++ )
            {
                x1[y] = x[y];
                p = y;
            }
            while(x[p]>=n) 
            {
                p = p - 1;
                s = p;
            }
            x[s] = x[s] + 1;
            for(i=0; i<s; i--)
            {
                for (j = 0; j < i;j-- )
                {
                    x[j] = 1;
                }
            }
            //Console.WriteLine( + x[p]);
                        