Изменения

* Находим находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта <tex>P</tex>,* К к оставшейся части дописываем максимально возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>),* Дописываем дописываем максимально возможный хвост.

{| cellpadding="3" style="margin-left: left; margin-right: left;"| [[Файл:Prevperm.png|600px|thumb|left|искомый суффикс (убывающая последовательность), элемент нарушающий последовательность, преобразование]]         |}

'''if''' (a[j] < > a[max]) '''and''' (a[j] < a[i])

swap(a[i], a[jmax])

== Специализация алгоритма для генерации предыдущей мультиперестановки =Мультиперестановка=Алгоритм полностью аналогичен генерации предыдущей перестановки* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность* Меняем его с максимальным элементом, меньшим нашего, стоящим правее* Перевернем правую часть ===Реализация=== '''int[]''' prevMultipermutation('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина перестановки</font> '''for''' i = n - 2 '''downto''' 0 '''if''' a[i] > a[i + 1] 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[j]) reverse(aто он выведет корректный результат, i + 1, n - 1) '''return''' a '''return''' ''null''то есть предыдущую мультиперестановку.

* Проходя справа налево, находим элемент <tex>t</tex> так, чтобы его разница со следующим отличалась более чем на единицу (пусть элемент с индексом <tex>0</tex> равен <tex>0</tex>, а первый элемент хранится в <tex>a[1]</tex>)

{| cellpadding="3" style="margin-left: left; margin-right: left;"| [[Файл:PrevChoose.png|600px|left|thumb|сочетания из n по k, элемент, который уменьшаем, максимальный хвост, преобразование]]       |}

a[0] = 0 <font color=green>// <tex>k</tex> {{---}} длина сочетания</font>

'''return''''' null''

<tex> 1) </tex> Последнее слагаемое можно разбить на два таких, отличающихся не более, чем на <tex>1</tex>, так чтобы наименьшее из них было больше предпоследнего слагаемого в разбиении. Тогда вместо последнего слагаемого мы запишем два найденных слагаемых.

<tex> 2) </tex> Если невозможен первый случай, то найдем такое слагаемое (не последнее), которое точно больше предыдущего на <tex>1</tex>. Обозначим его номер за <tex>j</tex>. Тогда <tex> a[j] = a[j] - 1 </tex>, а <tex> a[j + 1] = 1 + \sum_{i = j + 1}^n a[i] </tex>. А <tex> a[j + 1] </tex> будет последним слагаемым в разбиении.

Случай 1.Первый случай:{| cellpadding="3" style="margin-left: left; margin-right: left;"| [[Файл:Prevpart1.png|600px|leftthumb|2 < 9 / 2, значит разделим 9 на два слагаемых, 4 и 5]]|}Второй случай:{| cellpadding="3" style="margin-left: left; margin-right: left;"  Случай 2. | [[Файл:Prevpart2.png|600px|leftthumb|1 + 2 - наибольший префикс, который можно не изменять, уменьшаем первую 3, дописываем наибольший хвост - 9 ]]    |}

Первое слагаемое находится под индексом <tex>1</tex>.

'''if''' a[a.size- 1] / 2 >= a[a.size - 12] k = a[a.size- 1] a[a.size- 1] = a[a.size- 2] / 2

sum = a[na.size - 1];

'''return''''' null''

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|-| ||^||распределили сумму|}