8
правок
Изменения
→Специализация алгоритма для генерации следующего разбиения на подмножества
'''Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:'''
*Будем хранить подмножества в списке списков, например, разбиение <tex> \{1, 2, 3\}~ \{4, 5\}</tex> будет выглядеть так:
{| class="wikitable" border = 1
|}
* Будем поддерживать массив "удалённых" элементов {{---}} элементы , которые затем нужно будет вернуть в разбиение.
* Двигаясь снизу вверх будем рассматривать подмножества.
** Если мы можем дописать в текущее подмножество минимальный элемент из удалённых, то мы нашли следующее разбиение и нужно завершить цикл.
** Если дописать не можем, значит, либо нужно укоротить и заменить какой -то элемент в текущем подмножестве, либо перейти к следующему подмножеству. Будем идти справа налево и рассматривать элементы:
*** Если мы можем заменить текущий элемент минимальным удалённым {{---}} мы нашли следующее разбиение, завершаем оба цикла и выполняем алгоритм дальше. Стоит отметить, что нельзя перезаписывать последний элемент в подмножестве, иначе мы не сможем дописать минимальный хвост после этого подмножества {{---}} в удалённых будет элемент меньше текущего и мы не сможем выписать удаленные элементы так, чтобы получилось корректное разбиение.
*** Если заменить текущий элемент каким -то из удалённых нельзя, то следует удалить и этот.
* Допишем лексикографически минимальный хвост подмножеств из оставшихся удалённых элементов.
