Изменения

*Будем хранить подмножества в списке списков, например, разбиение <tex> \{1, 2, 3\}~ \{4, 5\}</tex> будет выглядеть так:

* Будем поддерживать массив удалённых элементов {{---}} элементы, которые затем нужно будет вернуть в разбиение. * Двигаясь снизу вверх будем рассматривать подмножества.** Если мы можем дописать в текущее подмножество минимальный элемент из удалённых, то мы нашли следующее разбиение и справа налевонужно завершить цикл.** Если дописать не можем, будем удалять элементызначит, записывая их либо нужно укоротить и заменить какой-то элемент в отдельный массивтекущем подмножестве, либо перейти к следующему подмножеству. Будем повторять эту операцию, пока не сможем выполнить одно из действий, описанных нижеидти справа налево и рассматривать элементы:** Заменить рассматриваемый * Если мы можем заменить текущий элемент уже удаленнымминимальным удалённым {{---}} мы нашли следующее разбиение, завершаем оба цикла и выполняем алгоритм дальше. Из всех подходящих элементов выбираем Стоит отметить, что нельзя перезаписывать последний элемент в подмножестве, иначе мы не сможем дописать минимальный. '''Важное замечание''': хвост после этого подмножества {{---}} в удалённых будет элемент меньше текущего и мы не можем заменить первый элемент подмножествасможем выписать удаленные элементы так, мы можем только удалить егочтобы получилось корректное разбиение.** Дополнить рассматриваемое подмножество уже удаленным элементом. Из всех подходящих элементов выбираем минимальный* Если заменить текущий элемент каким-то из удалённых нельзя, то следует удалить и этот.* Допишем лексикографически минимальный хвост подмножеств из оставшихся удалённых элементов.

used = '''list<int>''' <font color=green>// a {{---}} список, содержащий подмножества</font> <font color=green>// used {{---}} список, в котором мы храним удаленные элементы</font> used = '''list<int>''' fl = ''false'' '''for''' i = a.size - 1 '''downto''' 0 '''if''' (used.size != 0) '''and''' (max(used[used.size - 1] ) > a[i][a[i].size - 1]) <font color=green>// если в удалённых есть хотя бы один элемент, который мы можем добавить в конец подмножества элемент из used.</font> m = '''минимум из''' used '''строго больше''' a[i].add(used[used.size - 1] a[i].add(m) <font color=green>//добавляем</font> used.remove(used.size - 1m) '''break''' '''for''' j = a[i].size - 1 '''downto''' 0 '''if''' (used.size != 0) '''and''' (j != 0) '''and''' (max(used[used.size - 1] ) > a[i][j]) <font color=green>//если можем заменить элемент, другим элементом из списка used и он не последний</font> m = '''минимум из''' used '''строго больше''' a[i][-1] a[i][j] = used[used.size - 1] m <font color=green>//заменяем</font> used.remove(m) fl = ''true'' '''break''' '''if''' fl '''breakelse''' used.add(a[i][j-1]) <font color=green>//добавляем в used j-й элемент a[i-го подмножества</font> ].pop() '''if''' a[i].removesize == 0 a.pop(j) <font color=green>//удаляем j-й элемент i-го подмножества</font> '''if''' fl '''break''' <font color=green>//далее выведем все получившиеся подмножестваудалённые, которые не выбрали</font> sort(used) '''for''' i = 0 '''to''' used.size - 1 a.add('''list<int>'''(used[i])) <font color=green>//добавляем лексикографически минимальных хвост</font> '''return''' a</code>

| || || ||usedУдалённые элементы

|^|| || ||Удалили элемент 4. Так как он является первым последним в подмножестве, то мы не можем заменить его на другой.

|5|| || ||usedУдалённые элементы

|5|| || || ||usedУдалённые элементы

| || || || ||usedУдалённые элементы