107
правок
Изменения
→Специализация алгоритма для генерации предыдущего разбиения на слагаемые
== Специализация алгоритма для генерации предыдущего разбиения на слагаемые ==
Рассматриваемый алгоритм находит предыдущее [[комбинаторные объекты|разбиение на слагаемые]], при этом разбиение упорядоченно по возрастанию.
Рассмотрим два случая:
<tex> 1) </tex> Последнее слагаемое можно разбить на два таких, отличающихся не более, чем на 1, так чтобы наименьшее из них было больше предпоследнего слагаемого в разбиении. Тогда вместо последнего слагаемого мы запишем два найденных слагаемых.
<tex> 1) </tex> Если невозможен первый случай, то найдем такое слагаемое (не последнее), которое больше предыдущего на 1. Обозначим его номер за <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.
'''list<int>''' prevPartition('''list<int>''' b):
a[0] = 0
'''if''' a[a.size] / 2 >= a[a.size - 1]
k = a[a.size]
a[a.size] = a[a.size] / 2
a.push_back(k - a[a.size - 1])
'''return''' a
'''else'''
sum = a[n];
'''for''' i = a.size '''downto''' 1
'''if''' (i == 1) '''and''' (a[1] == 1)
'''return''' null
'''if''' a[i] > a[i - 1]
a[i]--
a[i + 1] = sum + 1
n = i + 1
'''return''' a
'''else'''
sum +=a[i]
a.pop_back();
