Получение предыдущего объекта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Специализация алгоритма для генерации предыдущего разбиения на слагаемые)
м (rollbackEdits.php mass rollback)
 
(не показано 58 промежуточных версий 6 участников)
Строка 5: Строка 5:
  
 
Отсюда понятен алгоритм:
 
Отсюда понятен алгоритм:
* Находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта <tex>P</tex>
+
* находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта <tex>P</tex>,
* К оставшейся части дописываем максимально возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>)
+
* к оставшейся части дописываем максимально возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>),
* Дописываем максимально возможный хвост
+
* дописываем максимально возможный хвост.
 
По построению получаем, что <tex>Q</tex> {{---}} минимально возможный.
 
По построению получаем, что <tex>Q</tex> {{---}} минимально возможный.
 +
 
== Специализация алгоритма для генерации предыдущего битового вектора ==
 
== Специализация алгоритма для генерации предыдущего битового вектора ==
[[Файл:Prevbitvector.png|200px|thumb|right|искомый суффикс, преобразование]]
 
 
 
* Находим минимальный суффикс, в котором есть <tex>1</tex>, его можно уменьшить, не изменяя оставшейся части
 
* Находим минимальный суффикс, в котором есть <tex>1</tex>, его можно уменьшить, не изменяя оставшейся части
 
* Вместо <tex>1</tex> записываем <tex>0</tex>  
 
* Вместо <tex>1</tex> записываем <tex>0</tex>  
 
* Дописываем максимально возможный хвост из единиц
 
* Дописываем максимально возможный хвост из единиц
  
 +
'''Пример:'''
 +
{| cellpadding="3" style="margin-left: left; margin-right: left;"
 +
| [[Файл:Prevbitvector.png|200px|thumb|искомый суффикс, преобразование]]
 +
|}
 +
===Реализация===
  
 
  '''int[]''' prevVector('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина вектора</font>
 
  '''int[]''' prevVector('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина вектора</font>
Строка 32: Строка 36:
 
* Перевернем правую часть
 
* Перевернем правую часть
  
 +
'''Пример:'''
 +
{| cellpadding="3" style="margin-left: left; margin-right: left;"
 +
| [[Файл:Prevperm.png|600px|thumb|искомый суффикс (убывающая последовательность), элемент нарушающий последовательность, преобразование]]
 +
|}
 +
===Реализация===
 
  '''int[]''' prevPermutation('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина перестановки</font>
 
  '''int[]''' prevPermutation('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина перестановки</font>
 
   '''for''' i = n - 2 '''downto''' 0
 
   '''for''' i = n - 2 '''downto''' 0
Строка 37: Строка 46:
 
       max = i + 1
 
       max = i + 1
 
       '''for''' j = i + 1 '''to''' n - 1
 
       '''for''' j = i + 1 '''to''' n - 1
         '''if''' (a[j] < a[max]) '''and''' (a[j] < a[i])
+
         '''if''' (a[j] > a[max]) '''and''' (a[j] < a[i])
 
           max = j
 
           max = j
       swap(a[i], a[j])
+
       swap(a[i], a[max])
 
       reverse(a, i + 1, n - 1)
 
       reverse(a, i + 1, n - 1)
 
       '''return''' a
 
       '''return''' a
 
   '''return''' ''null''
 
   '''return''' ''null''
[[Файл:Prevperm.png|600px|thumb|left|искомый суффикс( убывающая последовательность), элемент нарушающий последовательность, преобразование]]
 
  
 +
===Мультиперестановка===
 +
Если данный алгоритм применить к мультиперестановке, то он выведет корректный результат, то есть предыдущую мультиперестановку.
  
 +
== Специализация алгоритма для генерации предыдущего сочетания ==
  
  
 
+
* Проходя справа налево, находим элемент <tex>t</tex> так, чтобы его разница со следующим отличалась более чем на единицу (пусть элемент с индексом <tex>0</tex> равен <tex>0</tex>, а первый элемент хранится в <tex>a[1]</tex>)
 
 
 
 
 
 
 
 
 
 
== Специализация алгоритма для генерации предыдущей мультиперестановки ==
 
Алгоритм полностью аналогичен генерации предыдущей перестановки
 
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность
 
* Меняем его с максимальным элементом, меньшим нашего, стоящим правее
 
* Перевернем правую часть
 
 
 
'''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''
 
== Специализация алгоритма для генерации предыдущего сочетания ==
 
[[Файл:PrevChoose.png|500px|thumb|right|сочетания из n по k, элемент, который уменьшаем, максимальный хвост, преобразование]]* Проходя справа налево, находим элемент <tex>t</tex>, так чтобы его разница со следующим отличалась более чем на единицу
 
 
* уменьшаем его на единицу
 
* уменьшаем его на единицу
 
* дописываем максимально возможный хвост
 
* дописываем максимально возможный хвост
 
Если элемента <tex>t</tex> не существует, значит было дано первое сочетание. А значит и предыдущего сочетания не существует.
 
Если элемента <tex>t</tex> не существует, значит было дано первое сочетание. А значит и предыдущего сочетания не существует.
  
Пусть массив <tex>a</tex> хранит сочетания, так что первый элемент хранится в <tex>a[1]</tex>
+
Пусть массив <tex>a</tex> хранит сочетания так, что первый элемент хранится в <tex>a[1]</tex>
  
  int[] prevChoose('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} количество различных элементов</font>
+
'''Пример:'''
   a[0] = 0                       <font color=green>// <tex>k</tex> {{---}} длина сочетания</font>
+
{| cellpadding="3" style="margin-left: left; margin-right: left;"
   for i = k downto 1
+
| [[Файл:PrevChoose.png|600px|thumb|сочетания из n по k, элемент, который уменьшаем, максимальный хвост, преобразование]]
     if a[i] - a[i - 1] > 1
+
|}
 +
===Реализация===
 +
  '''int[]''' prevChoose('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} количество различных элементов</font>
 +
   a[0] = 0                 <font color=green>// <tex>k</tex> {{---}} длина сочетания</font>
 +
   '''for''' i = k '''downto''' 1
 +
     '''if''' a[i] - a[i - 1] > 1
 
       a[i]--
 
       a[i]--
 
       t = max(a[i] + 1, n - (k - i) + 1)
 
       t = max(a[i] + 1, n - (k - i) + 1)
       for j = i + 1 to k  
+
       '''for''' j = i + 1 '''to''' k  
 
         a[j] = t
 
         a[j] = t
 
         t++
 
         t++
       return a
+
       '''return''' a
   return null
+
   '''return''' ''null''
  
 
== Специализация алгоритма для генерации предыдущего разбиения на слагаемые ==
 
== Специализация алгоритма для генерации предыдущего разбиения на слагаемые ==
Рассматриваемый алгоритм находит предыдущее [[комбинаторные объекты|разбиение на слагаемые]], при этом разбиение упорядоченно по возрастанию.
+
Рассматриваемый алгоритм находит предыдущее [[комбинаторные объекты|разбиение на слагаемые]], при этом разбиение упорядочено по возрастанию.
  
 
Рассмотрим два случая:
 
Рассмотрим два случая:
  
<tex> 1) </tex> Последнее слагаемое можно разбить на два таких, отличающихся не более, чем на 1, так чтобы наименьшее из них было больше предпоследнего слагаемого в разбиении. Тогда вместо последнего слагаемого мы запишем два найденных слагаемых.  
+
<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> будет последним слагаемым в разбиении.
  
<tex> 2) </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.
+
Первый случай:
 +
{| cellpadding="3" style="margin-left: left; margin-right: left;"
 +
| [[Файл:Prevpart1.png|600px|thumb|2 < 9 / 2, значит разделим 9 на два слагаемых, 4 и 5]]
 +
|}
 +
Второй случай:
 +
{| cellpadding="3" style="margin-left: left; margin-right: left;"
 +
| [[Файл:Prevpart2.png|600px|thumb|1 + 2 - наибольший префикс, который можно не изменять, уменьшаем первую 3, дописываем наибольший хвост - 9 ]]
 +
|}
 +
=== Реализация ===
 +
Первое слагаемое находится под индексом <tex>1</tex>.
  
 
  '''list<int>''' prevPartition('''list<int>''' a):  
 
  '''list<int>''' prevPartition('''list<int>''' a):  
 
   a[0] = 0
 
   a[0] = 0
   '''if''' a[a.size] / 2 >= a[a.size - 1]
+
   '''if''' a[a.size - 1] / 2 >= a[a.size - 2]
     k = a[a.size]
+
     k = a[a.size - 1]
     a[a.size] = a[a.size] / 2
+
     a[a.size - 1] = a[a.size - 2] / 2
 
     a.push_back(k - a[a.size - 1])
 
     a.push_back(k - a[a.size - 1])
 
     '''return''' a
 
     '''return''' a
 
   '''else'''
 
   '''else'''
     sum = a[n];
+
     sum = a[a.size - 1];
 
     '''for''' i = a.size '''downto''' 1  
 
     '''for''' i = a.size '''downto''' 1  
 
       '''if''' (i == 1) '''and''' (a[1] == 1)
 
       '''if''' (i == 1) '''and''' (a[1] == 1)
         '''return''' null
+
         '''return''' ''null''
 
       '''if''' a[i] > a[i - 1]
 
       '''if''' a[i] > a[i - 1]
 
         a[i]--
 
         a[i]--
Строка 120: Строка 123:
 
         '''return''' a
 
         '''return''' a
 
       '''else'''
 
       '''else'''
         sum +=a[i]
+
         sum += a[i]
         a.pop_back();
+
         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
  
Случай 1.
+
'''Пример работы'''
[[Файл:Prevpart1.png|600px|left|2 < 9 / 2, значит разделим 9 на два слагаемых, 4 и 5]]
 
  
 +
Рассмотрим следующее разбиение:
 +
{| 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 Шаг:'''
  
Случай 2.
+
{| class="wikitable" border = 1
 +
|2||style="background:#FFCC00"|2
 +
|-
 +
| ||^||распределили сумму
 +
|}
  
[[Файл:Prevpart2.png|600px|left|1 + 2 - наибольший префикс, который можно не изменять, уменьшаем первую 3, дописываем наибольший хвост - 9 ]]
+
== См. также ==
 +
* [[Получение объекта по номеру]]
 +
* [[Получение номера по объекту]]
 +
* [[Получение следующего объекта]]
 +
== Источники информации ==
  
== Специализация алгоритма для генерации предыдущего разбиения на множества ==
+
* [http://rain.ifmo.ru/cat/view.php/vis/combinations/permutations-2000 Визуализатор перестановок]
 +
* [https://oeis.org/wiki/Orderings_of_partitions Orderings of partitions]
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Комбинаторика]]
 +
[[Категория: Генерация комбинаторных объектов]]

Текущая версия на 19:31, 4 сентября 2022

Алгоритм

Определение:
Получение предыдущего объекта — это нахождение объекта, предшествующего данному в лексикографическом порядке.

Объект [math]Q[/math] называется предыдущим за [math]P[/math], если [math]P \lt Q[/math] и не найдется такого [math]R[/math], что [math]P \lt R \lt Q[/math].

Отсюда понятен алгоритм:

  • находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта [math]P[/math],
  • к оставшейся части дописываем максимально возможный элемент (чтобы было выполнено правило [math]P \lt Q[/math]),
  • дописываем максимально возможный хвост.

По построению получаем, что [math]Q[/math] — минимально возможный.

Специализация алгоритма для генерации предыдущего битового вектора

  • Находим минимальный суффикс, в котором есть [math]1[/math], его можно уменьшить, не изменяя оставшейся части
  • Вместо [math]1[/math] записываем [math]0[/math]
  • Дописываем максимально возможный хвост из единиц

Пример:

искомый суффикс, преобразование

Реализация

int[] prevVector(int[] a): // [math]n[/math] — длина вектора
  while (n >= 0) and (a[n] != 1)
    a[n] = 1
    n--
  if n == -1
    return null
  a[n] = 0
  return a

Приведённый алгоритм эквивалентен вычитанию единицы из битового вектора.

Специализация алгоритма для генерации предыдущей перестановки

  • Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность
  • Меняем его с максимальным элементом, меньшим нашего, стоящим правее
  • Перевернем правую часть

Пример:

искомый суффикс (убывающая последовательность), элемент нарушающий последовательность, преобразование

Реализация

int[] prevPermutation(int[] a): // [math]n[/math] — длина перестановки
  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[max])
      reverse(a, i + 1, n - 1)
      return a
  return null

Мультиперестановка

Если данный алгоритм применить к мультиперестановке, то он выведет корректный результат, то есть предыдущую мультиперестановку.

Специализация алгоритма для генерации предыдущего сочетания

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

Если элемента [math]t[/math] не существует, значит было дано первое сочетание. А значит и предыдущего сочетания не существует.

Пусть массив [math]a[/math] хранит сочетания так, что первый элемент хранится в [math]a[1][/math]

Пример:

сочетания из n по k, элемент, который уменьшаем, максимальный хвост, преобразование

Реализация

int[] prevChoose(int[] a): // [math]n[/math] — количество различных элементов
  a[0] = 0                 // [math]k[/math] — длина сочетания
  for i = k downto 1
    if a[i] - a[i - 1] > 1
      a[i]--
      t = max(a[i] + 1, n - (k - i) + 1)
      for j = i + 1 to k 
        a[j] = t
        t++
      return a
  return null

Специализация алгоритма для генерации предыдущего разбиения на слагаемые

Рассматриваемый алгоритм находит предыдущее разбиение на слагаемые, при этом разбиение упорядочено по возрастанию.

Рассмотрим два случая:

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

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

Пример:

Первый случай:

2 < 9 / 2, значит разделим 9 на два слагаемых, 4 и 5

Второй случай:

1 + 2 - наибольший префикс, который можно не изменять, уменьшаем первую 3, дописываем наибольший хвост - 9

Реализация

Первое слагаемое находится под индексом [math]1[/math].

list<int> prevPartition(list<int> a): 
  a[0] = 0
  if a[a.size - 1] / 2 >= a[a.size - 2]
    k = a[a.size - 1]
    a[a.size - 1] = a[a.size - 2] / 2
    a.push_back(k - a[a.size - 1])
    return a
  else
    sum = a[a.size - 1];
    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()

Специализация алгоритма для генерации предыдущего разбиения на множества

Рассматриваемый алгоритм находит предыдущее разбиение на множества.

Пусть нам надо получить разбиение некого множества непомеченных элементов, например, разложить одинаковые шары по коробкам. Пусть множества упорядочены по убыванию мощностей, а разбиения упорядочены лексикографически следующим образом. Разбиение [math]A = A_1 \cup A_2 \cup . . . \cup A_k[/math] лексикографически меньше разбиения [math]B = B_1 \cup B_2 \cup . . . \cup B_l[/math] если существует такое [math]i[/math], что [math]A_1 = B_1, A_2 = B_2, . . . ,A_{i - 1} = B_{i - 1}, A_i \lt B_i[/math].

Пример упорядоченного списка разбиений множества из [math] 6[/math] элементов:

[math]\{\{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\}\}[/math]

Рассмотрим алгоритм нахождения лексикографически предыдущего разбиения на подмножества:

  • Будем хранить подмножества в списке , например, разбиение [math] \{3, 1, 1, 1\}[/math] будет выглядеть так:
3 1 1 1

Будем идти справа налево и применять следующий алгоритм:

  • Найдём множество [math] i[/math] минимальной мощности [math] m_i[/math], которое можно разбить на два множества, мощности которых равны [math] m_i - 1[/math] и [math] 1 [/math] соответственно
  • Если [math] i [/math] — первый элемент, то мы не можем добавить единицу никуда правее, следовательно предыдущее разбиение должно состоять из множеств, мощности которых [math]{ } \le m_i - 1[/math]
  • Иначе исключим [math] 1[/math] элемент из [math] i[/math] —ого множества и добавим его к [math] i - 1[/math] множеству(при условии что мощность [math] i - 1[/math] множества не станет больше [math] m_i - 1[/math], иначе создадим множество из [math] 1[/math] элемента)

Реализация

list<int> PreviousSetPartition(list<int> a) 
 for int i = a.size - 1 downto 0     // найдем минимальный элемент, от которого можно отнять 1
  if a[i] > 1
     a[i] --
     if i > 0                     // см 2 пункт алгоритма 
       if  i + 1 < a.size         // если справа есть еще элементы  
         a[i + 1] ++
       else a.push_back(1)
     else int sum = 1             // пройдемся до конца массива и найдем сумму оставшихся элементов 
      for j = i + 1 to a.size
        sum += a[j]
      while a[a.size] != a[0]     // удалим все элементы кроме 1, чтобы заполнить теми, что не превышают a[0] 
        a.pop_back
      while sum > a[0]
        sum -= a[0]
        a.push(a[0])                   
      if sum != 0
       a.push(sum);
  break                  // break нужен для того, чтобы мы остановились после первого подходящего элемента 
 return a

Пример работы

Рассмотрим следующее разбиение:

3 1

1 Шаг:

3 1
^ 3 — наименьший элемент, от которого мы можем отнять 1, однако 3 также является первым элементом, значит предыдущее разбиение должно состоять из элементов [math]\le 2 [/math].

2 Шаг:

2 1
^ уменьшили 3 на 1, прошли до конца списка, вычислили сумму оставшихся элементов, которую теперь надо распределить на элементы [math]\le 2 [/math]
1 1 sum

3 Шаг:

2
^ удалили все элементы кроме первого

4 Шаг:

2 2
^ распределили сумму

См. также

Источники информации