1632
правки
Изменения
м
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();
==Специализация алгоритма для генерации предыдущего разбиения на множества==
Рассматриваемый алгоритм находит предыдущее [[комбинаторные объекты|разбиение на множества]].
Пусть нам надо получить разбиение некого множества непомеченных элементов, например, разложить одинаковые шары по коробкам.
Пусть множества упорядочены по убыванию мощностей, а разбиения упорядочены лексикографически следующим образом. Разбиение <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> \{3, 1, 1, 1\}</tex> будет выглядеть так:
{| 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 Шаг:'''
{| class="wikitable" border = 1
|3||1
|-
|^|| || 3 {{---}} наименьший элемент, от которого мы можем отнять 1, однако 3 также является первым элементом, значит предыдущее разбиение должно состоять из элементов <tex>\le 2 </tex>.
|}
'''2 Шаг:'''
{| 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 Шаг:'''
{| class="wikitable" border = 1
|2||style="background:#FFCC00"|2
|-
| ||^||распределили сумму
|}
== См. также ==
* [http://rain.ifmo.ru/cat/view.php/vis/combinations/permutations-2000 Визуализатор перестановок]
* [https://oeis.org/wiki/Orderings_of_partitions Orderings of partitions]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Генерация комбинаторных объектов]]
