76
правок
Изменения
→Специализация алгоритма для генерации следующего разбиения на подмножества
'''Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:'''
*Будем хранить подмножества в списке списков, например, разбиение <tex> \{1, 2, 3\}~ \{4, 5\}</tex> будет выглядеть так:
{| class="wikitable" border = 1
<code>
'''function''' nextSetsnextSetPartition(a:list<list<int>>):list<list<int>>;
// a - список, содержащий подмножества
// used - список, в котором мы храним удаленные элементы
used = list<int>();
fl = ''false''
'''for''' i = a.size - 1 '''downto''' 0
'''if''' used[used.size] > a[i][a[i].size] '''then''' //если можем добавить в конец подмножества элемент из used a[i].add(used[used.size]); //добавляем
'''break'''
'''for''' j = a[i].size - 1 '''downto''' 0
'''if''' (j <> 1) and used[used.size] > a[i][j] '''then''' //если можем заменить элемент, другим элементом из списка used a[i][j] = used[used.size]; //заменяем
fl = ''true''
'''break'''
used.add(a[i][j]) ; a[i].pop(j); // удаляем j элемент i подмножества и добавляем его в список
'''if''' (fl) '''break'''
// далее выведем все получившиеся подмножества
sort(used)
'''for''' i = 0 '''to''' used.size - 1
return(a);
</code>
