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> 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 '''todownto''' 0 <font color = green> // найдем минимальный элемент, от которого можно отнять 1</font>
'''if''' a[i] > 1
a[i] --
'''else''' a.push_back(1)
'''else''' int sum = 1 <font color = green> // пройдемся до конца массива и найдем сумму оставшихся элементов </font>
'''whilefor''' j = i < + 1 '''to''' a.size - 1 i++ sum += a[ij]
'''while''' a[a.size] != a[0] <font color = green> // удалим все элементы кроме 1, чтобы заполнить теми, что не превышают a[0] </font>
a.pop_back
'''while''' sum > ba[10]
sum -= a[0]
a.push(a[0])
'''Пример работы'''
Рассмотрим следующее разбиение:
{| class="wikitable" border = 1
|3||1
|3||1
|-
|^|| || 3 {{---}} наименьший элемент, от которого мы можем отнять 1, однако 3 также является первым элементом, значит предыдущее разбиение должно состоять из элементов, меньших либо равных <tex>\le 2</tex>.
|}
