combinat - Программирование на языке C++

17 Построение комбинаторных объектов

Определение стуктуры для построения всех комбинаторных объектов на примере стуктуры BinarySequence (построение всех двоичных последовательностей заданной длины):

     #include<iostream>
     using namespace std;
     
     struct BinarySequence
     {
         int n; // Длина последовательности
         int * elems; // Массив для хранения элементов последовательности
     
         void SetFirst() // Данный метод генерирует самую первую
         {               // последовательность - из одних нулей
             for(int i=0;i<n;++i)
                 elems[i]=0;
         }
     
         void SetLast() // Данный метод генерирует самую последнюю
         {              // последовательность - из одних единиц
             for(int i=0;i<n;++i)
                 elems[i]=1;
         }
     
         BinarySequence() // Конструктор по умолчанию - создается
         {                // последовательность длины 1
             n=1;
             elems=new int[1];
             SetFirst();
         }
     
         BinarySequence(int size) // Конструктор для создания последовательности
         {                        // заданной длины
             n=size;
             elems=new int[n];
             SetFirst();
         }
     
         ~BinarySequence() // Деструктор для корректного освобождения памяти
         {                 // Вызывается автоматически при удалении объекта
             delete elems;
         }
     
         bool Next () // Данный метод генерирует из текущей строки следующую
                      // и возвращает true, если это удалось, иначе false
         { // КОД НАПИШИТЕ САМИ
         }
     
         bool Previous () // Данный метод генерирует из текущей строки предыдущую
                      // и возвращает true, если это удалось, иначе false
         { // КОД НАПИШИТЕ САМИ
         }
     };
     
     // Теперь определяем вывод на экран
     ostream & operator<<(ostream & out, const BinarySequence & Seq)
     {
         for(int i=0;i<Seq.n;++i)
             out<<Seq.elems[i];
         return out;
     }
     
     int main()
     {
         int n;
         cin>>n;                 // Считали n - длину строки
         BinarySequence Seq(n);  // Создали объект для строк длины n
         do
         {
             cout<<Seq<<endl;    // Выводим последовательность на экран
         }
         while( Seq.Next() )     // И генерируем следующую строку пока возможно
         return 0;
     }

Упражнения

(А) По данному числу n выведите все строки длины n из нулей и единиц в лексикографическом порядке.
(B) По данному числу n выведите все строки длины n из нулей и единиц в обратном лексикографическом порядке.
(C) По данным числам n и k, k≤10 выведите все строки длины n из символов 0..k-1 в лексикографическом порядке.
(D) По данным числам n и k, k≤36 выведите все строки длины n из символов 0..k-1 в обратном лексикографическом порядке. Вместо значений 10, 11, ..., 35 необходимо выводить латинские буквы a, ..., z соответственно.
(E) По данным числам n и k, 0≤k≤n, n>0 выведите все строки из нулей и единиц длины n, содержащие ровно k единиц в лексикографическом порядке. Пример вывода для n=4 и k=2.:
```
          0011
          0101
          0110
          1001
          1010
          1100
```
(F) Под данному числу n, 0<n<10 выведите все перестановки чисел от 1 до n в лексикографическом порядке. Перестановки выводятся по одной в строке, числа в перестановке выводятся без пробелов. Пример вывода для n=3:
```
          123
          132
          213
          231
          312
          321
```
(G) Для данного слова (последовательности строчных латинских букв) выведите следующее за ним (в лексикографическом порядке) слово, которое может быть получено из данного перестановкой букв (анаграмму). Если из данное слово уже является последним среди всех своих анаграмм, то необходимо вывести первую возможную (в лексикографическом порядке) анаграмму. Программа получает на вход последовательность слов по одному слову в строке и должна вывести для каждого полученного на вход слова результат.
Пример:
```
          Вход
          aab
          aba
          baa
          aaa
          
          Выход
          aba
          baa
          aab
          aaa
```
(H) Для данных чисел n и k выведите все возрастающие последовательности длины k из чисел n в лексикографическом порядке. Последовательности выводятся по одной в строке, числа внутри последовательностей разделяются пробелами. Пример:
```
          Вход
          5 2
          
          Выход
          1 2
          1 3
          1 4
          1 5
          2 3
          2 4
          2 5
          3 4
          3 5
          4 5
```
(I) Для данных чисел n и k выведите все убывающие последовательности длины k из чисел n в лексикографическом порядке. Последовательности выводятся по одной в строке, числа внутри последовательностей разделяются пробелами. Пример:
```
          Вход
          5 2
          
          Выход
          2 1
          3 1
          3 2
          4 1
          4 2
          4 3
          5 1
          5 2
          5 3
          5 4
```
(J) Дано натуральное число n. Рассмотрим его разбиение на различные натуральные слагаемые. Два разбиения, отличающихся только порядком слагаемых будем считать за одно, поэтому можно считать, что слагаемые в разбиении упорядочены по невозрастанию.
Выведите все разбиения в лексикографическом порядке. Пример:
```
          Вход
          5
          
          Выход
          1 1 1 1 1
          2 1 1 1
          2 2 1
          3 1 1
          3 2
          4 1
          5
```

(K) Решите предыдущую задачу для обратного лексикографического порядка.

(L) Решите задачу вывода всех представлений числа в виде суммы, если слагаемые упорядочены по неубыванию, а порядок вывода самих слагаемых – лексикографический.
```
          Вход
          5
          
          Выход
          1 1 1 1 1
          1 1 1 2
          1 1 3
          1 2 2
          1 4
          2 3
          5
```

(M) Решите предыдущую задачу для обратного лексикографического порядка.

(N) Дано число n. Определите, сколькими способами можно расставить на доске n×n n ферзей, не бьющих друг друга. Пример:
```
          Вход
          8
          
          Выход
          92
```
Также напишите программу, которая будет выводить все возможные расстановки.
(O) Решите предыдущую задачу, если расстановки ферзей, которые можно получить друг из друга поворотами и отражениями доски считать за одно.
```
          Вход
          8
          
          Выход
          12
```