1632
правки
Изменения
м
Разбиения Пусть нам надо получить разбиение некого множества непомеченных элементов, например, разложить одинаковые шары по коробкам. Пусть множества упорядочены по возрастанию убыванию мощностей наибольших множеств данного , а разбиения упорядочены лексикографически следующим образом. Разбиение <tex>A = A_1 \cup A_2 \cup . . . \cup A_k</tex> лексикографически меньше разбиения<tex>B = B_1 \cup B_2 \cup . . . \cup B_l</tex> если существует такое <tex>i</tex>, а внутри что <tex>A_1 = B_1, A_2 = B_2, . . . ,A_{i - 1} = B_{i - 1}, A_i < B_i</tex>. '''Пример упорядоченного списка разбиений множества упорядочены по убыванию мощностей.из <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> 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> будет выглядеть так:
Глядя на пример нетрудно придумать Будем идти справа налево и применять следующий алгоритм, позволяющий найти предыдущее разбиение:
'''то''' {| class="wikitable" border = 1|3||1|-|^|| || 3 {{---}} наименьший элемент, от которого мы можем отнять 1, однако 3 также является первым элементом, значит предыдущее разбиение должно состоять из множеств, мощности которых элементов <tex>{ } \le m_i - 12 </tex>.
Псевдокод '''vector<int>b''' PreviousSetPartition(vector<int>a) '''for''' int i {| class="wikitable" border = a.size - 1 '''to''' 0 '''if''' a[i] > 1 '''if''' i > 0 <font color |2||style= green> // см "background:#FFCC00"|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|}
rollbackEdits.php mass rollback
max = i + 1
'''for''' j = i + 1 '''to''' n - 1
'''if''' (a[j] < > a[max]) '''and''' (a[j] < a[i])
max = j
swap(a[i], a[jmax])
reverse(a, i + 1, n - 1)
'''return''' a
'''return''' ''null''
===Мультиперестановка===
Если данный алгоритм применить к мультиперестановке, то он выведет корректный результат, то есть предыдущую мультиперестановку.
'''else'''
sum += a[i]
a.pop_back();
==Специализация алгоритма для генерации предыдущего разбиения на множества==
Рассматриваемый алгоритм находит предыдущее [[комбинаторные объекты|разбиение на множества]].
{| class="wikitable" border = 1
|3||1||1||1
|}
*Найдём множество <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 '''downto''' 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> '''for''' j = i + 1 '''to''' a.size sum += a[j] '''while''' a[a.size] != a[0] <font color = green> // удалим все элементы кроме 1, чтобы заполнить теми, что не превышают a[0] </font> a.pop_back '''while''' sum > a[0] sum -= a[0] a.push(a[0]) '''if''' sum != 0 a.push(sum); '''break''' <font color = green> // break нужен для того, чтобы мы остановились после первого подходящего элемента </font> '''return''' a '''Пример работы''' Рассмотрим следующее разбиение: {| class="wikitable" border = 1|3||1|}'''1 Шаг:'''
|}'''Иначе2 Шаг:''' исключить <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
|style="background:#FFCC00"|2||1
|-
| ||^||уменьшили 3 на 1, прошли до конца списка, вычислили сумму оставшихся элементов, которую теперь надо распределить на элементы <tex>\le 2 </tex>
|-
|1||1||sum
|}
'''3 Шаг:'''
{| class="wikitable" border = 1
|2||style="background:#FFCC00"| ||
|-
|^|| ||удалили все элементы кроме первого
|}
'''4 Шаг:'''
== См. также ==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Генерация комбинаторных объектов]]
