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