39
правок
Изменения
→Специализация алгоритма для генерации предыдущего разбиения на множества
==Специализация алгоритма для генерации предыдущего разбиения на множества==
Рассматриваемый алгоритм находит предыдущее [[комбинаторные объекты|разбиение на множества]].
Разбиения упорядочены по возрастанию мощностей наибольших множеств данного разбиения, а внутри разбиений множества упорядочены по убыванию мощностей.
Пример упорядоченного списка разбиений множества из <tex> 6</tex> элементов
{{1, 1, 1, 1, 1, 1}, {2, 1, 1, 1, 1}, {2, 2, 1, 1}, {2, 2, 2}, {3, 1, 1, 1}, {3, 2, 1}, {3, 3}, {4, 1, 1}, {4, 2}, {5, 1}, {6}}
Глядя на пример нетрудно придумать алгоритм, позволяющий найти предыдущее разбиение:
*Найдём множество <tex> i</tex> минимальной мощности <tex> m_i</tex>, которое можно разбить на два множества, мощности которых равны <tex> m_i - 1</tex> и <tex> 1 </tex> соответственно
*'''Если''' <tex> i {-}</tex> наибольшее множество в этом разбиении,
'''то''' предыдущее разбиение должно состоять из множеств, мощности которых <tex>{ } \le m_i - 1</tex>
'''Иначе''' исключить <tex> 1</tex> элемент из <tex> i</tex> -ого множества и добавить его к <tex> i - 1</tex> множеству(при условии что мощность <tex> i - 1</tex> множества не станет больше <tex> m_i - 1</tex>, иначе создать множество из <tex> 1</tex> элемента)
Псевдокод
'''vector<int>b''' PreviousSetPartition(vector<int>a)
'''for''' int i = a.size - 1 '''to''' 0
'''if''' a[i] > 1
'''if''' i > 0 <font color = green> // см 2 пункт алгоритма (a[0] - наибольшее множество)</font>
a[i] --
'''if''' i + 1 < a.size <font color = green> // если есть еще элементы кроме a[0] </font>
a[i + 1] ++
'''else''' a.push_back(1)
'''else''' int sum = a[0]
'''while''' i < a.size - 1
i++
sum += a[i]
'''while''' a[a.size] != a[0]
a.pop_back
'''while''' sum > b[1]
sum -= a[0]
a.push(a[0]) <font color = green> // см 2 пункт алгоритма, необходимо забить вектор элементами, мощность которых <= a[0] </font>
'''if''' sum != 0
a.push(sum);
return a
== См. также ==
