Перебор комбинаторных объектов - 2

В этом листке будет реализован другой подход к построению комбинаторных объектов.

Вместо рекурсивной реализации необходимо реализовать следующие методы.

1. Построение первого в лексикографическом порядке объекта.
2. Для любого данного объекта построение следующего за ним объекта.

При этом все должно быть реализовано с использованием технологии объектно-ориентированного программирования и перегрузки операторов. А именно, для каждого класса комбинаторых объектов должен быть реализован собственный класс (структура), содержащие следующие обязательные методы:

1. Конструктор. Вызывается автоматически при создании объекта без параметров.
2. Конструктор с параметрами. Как правило, в качестве параметра будет передаваться размер объекта.
3. Оператор ++, генерирующий следующую последовательность. Метод возвращает значение типа bool: true. если построение было удачно и false, если неудачно (т.е. последовательность уже максимальная в лексикографическом порядке).
4. Перегруженный оператор для вывода результата в поток типа ostream.

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

class binary_sequence
{
    vector<int> m_elems;

 public:
    binary_sequence(int size = 1, int fill = 0) // Конструктор для создания последовательности
    {                                          // заданной длины
        m_elems.resize(size, fill);
    }

    int size()
    {
        return m_elems.size();
    }

    bool operator++() // Данный метод генерирует из текущей строки следующую
                      // и возвращает true, если это удалось, иначе false
    { // КОД НАПИШИТЕ САМИ
    }

    bool operator--() // Данный метод генерирует из текущей строки предыдущую
                      // и возвращает true, если это удалось, иначе false
    { // КОД НАПИШИТЕ САМИ
    }

    friend ostream & operator<<(ostream &, const binary_sequence &);
};

// Теперь определяем вывод на экран
ostream & operator<<(ostream & out, const binary_sequence & seq)
{
    for (int i = 0; i < seq.size(); ++i)
        out << seq.m_elems[i] << " ";
    return out;
}

int main()
{
    int n;
    cin >> n;         // Считали n - длину строки
    binary_sequence seq(n);  // Создали объект для строк длины n
    cout << seq << endl;
    while (++seq)
        cout << seq << endl;
    return 0;
}

Во всех задачах этого листка необходимо сгенерировать все числовые последовательности, удовлетворяющие условию, в лексикографическом или обратном лексикографическом порядке. Ввод-вывод стандартный. Каждая последовательность должна выводиться в отдельной строке, вывод должен завершаться символом новой строки. Числа, входящие в последовательность, должны быть разделены одним пробелом (если в условии не оговорено иное). В начале и конце каждой строки допускаются пробелы.

Упражнения

A: Двоичные последовательности

По данному натуральному n≤10 выведите все двоичные последовательности длины n в лексикографическом порядке.

3

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

B: Двоичные последовательности в обратном порядке

По данному натуральному n≤10 выведите все двоичные последовательности длины n в обратном лексикографическом порядке.

3

1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0

C: Двоичные последовательности без двух единиц подряд

По данному натуральному \(n\) выведите все двоичные последовательности длины \(n\), не содержащие двух единиц подряд, в лексикографическом порядке.

3

0 0 0
0 0 1
0 1 0
1 0 0
1 0 1

D: Двоичные последовательности без двух единиц подряд в обратном лексикографическом порядке

По данному натуральному \(n\) выведите все двоичные последовательности длины \(n\), не содержащие двух единиц подряд, в обратном лексикографическом порядке.

3

1 0 1
1 0 0
0 1 0
0 0 1
0 0 0

E: Двоичные последовательности длины n содержащие k единиц

По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные последовательности длины n, содержащие ровно k единиц в лексикографическом порядке.

4 2

0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0

F: Двоичные последовательности длины n содержащие k единиц в обратном порядке

По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные последовательности длины n, содержащие ровно k единиц в обратном лексикографическом порядке.

4 2

1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 1

G: Двоичные последовательности длины n содержащие k единиц без двух единиц подряд

По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные строки длины n содержащие k единиц и не содержащие двух единиц подряд в лексикографическом порядке.

4 2

0 1 0 1
1 0 0 1
1 0 1 0

H: Двоичные последовательности длины n содержащие k единиц без двух единиц подряд в обратном порядке

По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные строки длины n содержащие k единиц и не содержащие двух единиц подряд в обратном лексикографическом порядке.

4 2

1 0 1 0
1 0 0 1
0 1 0 1

I: Возрастающие последовательности

По данным натуральным n и k (n≤k) выведите все возрастающие последовательности длины n, состоящие из чисел 1..k в лексикографическом порядке.

3 5

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

J: Возрастающие последовательности в обратном порядке

По данным натуральным n и k (n≤k) выведите все возрастающие последовательности длины n, состоящие из чисел 1..k в обратном лексикографическом порядке.

3 5

3 4 5
2 4 5
2 3 5
2 3 4
1 4 5
1 3 5
1 3 4
1 2 5
1 2 4
1 2 3

K: Убывающие последовательности

По данным натуральным n и k (n≤k) выведите все убывающие последовательности длины n, состоящие из чисел 1..k в лексикографическом порядке.

3 5

3 2 1
4 2 1
4 3 1
4 3 2
5 2 1
5 3 1
5 3 2
5 4 1
5 4 2
5 4 3

L: Убывающие последовательности в обратном поряде

По данным натуральным n и k (n≤k) выведите все убывающие последовательности длины n, состоящие из чисел 1..k в обратном лексикографическом порядке.

3 5

5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1

M: Перестановки

Дано натуральное число n. Выведите всевозможные перестановки чисел от 1 до n в лексикографическом порядке.

3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

N: Перестановки в обратном лексикографическом порядке

Дано натуральное число n. Выведите всевозможные перестановки чисел от 1 до n в обратном лексикографическом порядке.

3

3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3

O: Следующее слово

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

aab
aba
baa
aaa

aba
baa
aab
aaa

P: Правильные скобочные последовательности

Дано натуральное числo n. Выведите все правильные скобочные последовательности, состоящие из n открывающихся круглых скобок и n закрывающихся скобок в лексикографическом порядке.

3

((()))
(()())
(())()
()(())
()()()

Q: Правильные скобочные последовательности в обратном порядке

Дано натуральное числo n. Выведите все правильные скобочные последовательности, состоящие из n открывающихся круглых скобок и n закрывающихся скобок в обратном лексикографическом порядке.

3

()()()
()(())
(())()
(()())
((()))

R: Разбиение на невозрастающие слагаемые

Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке невозрастания. Сами разбиения необходимо выводить в лексикографическом порядке.

5

1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5

S: Разбиение на невозрастающие слагаемые в обратном порядке

Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке невозрастания. Сами разбиения необходимо выводить в обратном лексикографическом порядке.

5

5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

T: Разбиение на неубывающие слагаемые

Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке неубывания. Сами разбиения необходимо выводить в лексикографическом порядке.

5

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

U: Разбиение на неубывающие слагаемые в обратном порядке

Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке неубывания. Сами разбиения необходимо выводить в обратном лексикографическом порядке.

5

5
2 3
1 4
1 2 2
1 1 3
1 1 1 2
1 1 1 1 1

V: Разбиение на k невозрастающих слагаемых

Даны натуральные числа n и k (1≤k≤n). Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке невозрастания. Сами разбиения необходимо выводить в лексикографическом порядке.

8 3

3 3 2
4 2 2
4 3 1
5 2 1
6 1 1

W: Разбиение на k невозрастающих слагаемых в обратном порядке

Даны натуральные числа n и k (1≤k≤n). Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке невозрастания. Сами разбиения необходимо выводить в обратном лексикографическом порядке.

8 3

6 1 1
5 2 1
4 3 1
4 2 2
3 3 2

X: Разбиение на k неубывающих слагаемых

Даны натуральные числа n и k (1≤k≤n). Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке неубывания. Сами разбиения необходимо выводить в лексикографическом порядке.

8 3

1 1 6
1 2 5
1 3 4
2 2 4
2 3 3

Y: Разбиение на k неубывающих слагаемых в обратном порядке

Даны натуральные числа n и k (1≤k≤n). Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке неубывания. Сами разбиения необходимо выводить в обратном лексикографическом порядке.

8 3

2 3 3
2 2 4
1 3 4
1 2 5
1 1 6