Перебор комбинаторных объектов - 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≤kn, 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≤kn, 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≤kn, n≥1) выведите все двоичные строки длины n содержащие k единиц и не содержащие двух единиц подряд в лексикографическом порядке.

Ввод Вывод
4 2
0 1 0 1
1 0 0 1
1 0 1 0

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

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

Ввод Вывод
4 2
1 0 1 0
1 0 0 1
0 1 0 1

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

По данным натуральным n и k (nk) выведите все возрастающие последовательности длины 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 (nk) выведите все возрастающие последовательности длины 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 (nk) выведите все убывающие последовательности длины 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 (nk) выведите все убывающие последовательности длины 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≤kn). Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке невозрастания. Сами разбиения необходимо выводить в лексикографическом порядке.

Ввод Вывод
8 3
3 3 2
4 2 2
4 3 1
5 2 1
6 1 1

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

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

Ввод Вывод
8 3
6 1 1
5 2 1
4 3 1
4 2 2
3 3 2

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

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

Ввод Вывод
8 3
1 1 6
1 2 5
1 3 4
2 2 4
2 3 3

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

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

Ввод Вывод
8 3
2 3 3
2 2 4
1 3 4
1 2 5
1 1 6