Изменения

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

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>

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