Изменения

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

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(mused.size - 1) '''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][j] = used[used.size -1] a[i][j] = m <font color=green>//заменяем</font> used.remove(m) fl = ''true'' '''break''' '''if''' fl '''elsebreak''' used.add(a[i][-1j]) <font color=green>//добавляем в used j-й элемент i-го подмножества</font> a[i].popremove(j) '''if''' a[ <font color=green>//удаляем j-й элемент i].size == 0-го подмножества</font> a.pop() '''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. Так как он является последним первым в подмножестве, то мы не можем заменить его на другой.