Изменения

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

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

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>

Глядя на пример нетрудно придумать {| class="wikitable" border = 1|3||1||1||1|} Будем идти справа налево и применять следующий алгоритм, позволяющий найти предыдущее разбиение:

*'''Если''' <tex> i </tex> {{---}} первый элемент, '''то''' мы не можем добавить единицу никуда правее, следовательно предыдущее разбиение должно состоять из множеств, мощности которых <tex>{ }\le m_i - 1</tex> наибольшее множество в этом разбиении,

*'''тоИначе''' предыдущее разбиение должно состоять исключим <tex> 1</tex> элемент из множеств, мощности которых <tex> i</tex>{ {---} \le }ого множества и добавим его к <tex> i - 1</tex> множеству(при условии что мощность <tex> i - 1</tex> множества не станет больше <tex> m_i - 1</tex>, иначе создадим множество из <tex> 1</tex> элемента)

===Реализация=== '''Иначеlist<int>'''PreviousSetPartition('' исключить 'list<texint> ''' a) '''for''' int i = a.size - 1'''downto''' 0 <font color = green> //tex> найдем минимальный элемент из , от которого можно отнять 1<tex/font> '''if''' a[i] > 1 a[i] -- '''if''' i> 0 <font color = green> /tex> -ого множества и добавить его к / см 2 пункт алгоритма <tex/font> '''if''' i - + 1<a.size <font color = green> /tex/ если справа есть еще элементы </font> множеству a[i + 1] ++ '''else''' a.push_back(при условии что мощность 1) '''else''' int sum = 1 <font color = green> // пройдемся до конца массива и найдем сумму оставшихся элементов <tex/font> '''for''' j = i - + 1'''to''' a.size sum += a[j] '''while''' a[a.size] != a[0] <font color = green> //tex> множества удалим все элементы кроме 1, чтобы заполнить теми, что не станет больше превышают a[0] <tex/font> m_i a.pop_back '''while''' sum > a[0] sum - 1= a[0] a.push(a[0]) '''if''' sum != 0 a.push(sum); '''break''' <font color = green> //tex>break нужен для того, иначе создать множество из чтобы мы остановились после первого подходящего элемента <tex/font> '''return''' a '''Пример работы''' Рассмотрим следующее разбиение: {| class="wikitable" border = 1</tex> элемента)|3||1|}'''1 Шаг:'''

Псевдокод|} '''vector<int>b2 Шаг:''' PreviousSetPartition(vector<int>a) '''for''' int i {| class="wikitable" border = a.size - 1 '''to''' 0 '''if''' a[i] > |style="background:#FFCC00"|2||1 '''if''' i > 0 |-| ||^||уменьшили 3 на 1, прошли до конца списка, вычислили сумму оставшихся элементов, которую теперь надо распределить на элементы <font color = greentex> // см \le 2 пункт алгоритма (a[0] - наибольшее множество)</fonttex> a[i] -|- '''if''' i + |1||1 < a.size <font color = green> // если есть еще элементы кроме a[0] </font>||sum a[i + 1] ++|} '''else3 Шаг:''' a.push_back(1) '''else''' int sum {| class="wikitable" border = a[0]1 |2||style="background:#FFCC00"| || '''while''' i < a.size |- 1 i++|^|| ||удалили все элементы кроме первого sum += a[i]|} '''while4 Шаг:''' a[a.size] != a[0] a.pop_back '''while''' sum > b[{| class="wikitable" border = 1] sum -= a[0] a.push(a[0]) <font color |2||style= green> // см "background:#FFCC00"|2 пункт алгоритма, необходимо забить вектор элементами, мощность которых <= a[0] </font> '''if''' sum != 0|- a.push(sum);| ||^||распределили сумму return a|}