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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Определение == В комбинаторике перестано́вка — это упорядоченный набор чисел обычно тр…»)
 
(Специализация алгоритма для генерации следующего сочетания)
 
(не показано 239 промежуточных версий 22 участников)
Строка 1: Строка 1:
== Определение ==
 
В комбинаторике перестано́вка — это упорядоченный набор чисел  обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки.
 
  
----
+
== Алгоритм ==
 +
{{Определение|definition= '''Получение следующего объекта''' {{---}} это нахождение объекта, следующего за данным в [[Лексикографический порядок|лексикографическом порядке]].
 +
}}
 +
Объект <tex>Q</tex> называется следующим за <tex>P</tex>, если <tex>P < Q</tex> и не найдется такого <tex>R</tex>, что <tex>P < R < Q</tex>.
  
== Перебор перестановок в лексикографическом порядке ==
+
Отсюда понятен алгоритм:
 +
* находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта <tex>P</tex>,
 +
* к оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>),
 +
* дописываем минимальный возможный хвост.
 +
По построению получаем, что <tex>Q</tex> {{---}} минимально возможный.
  
Каждая следующая перестановка строится следующим образом:
+
== Специализация алгоритма для генерации следующего битового вектора ==
 +
* Находим минимальный суффикс, в котором есть <tex>0</tex>, его можно увеличить, не меняя оставшейся части
 +
* Вместо <tex>0</tex> записываем <tex>1</tex>
 +
* Дописываем минимально возможный хвост из нулей
 +
'''int[]''' nextVector('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина вектора</font>
 +
  '''while''' (n >= 0) '''and''' (a[n] != 0)
 +
      a[n] = 0
 +
      n--
 +
  '''if''' n == -1
 +
    '''return''' ''null''
 +
  a[n] = 1
 +
  '''return''' a
 +
Приведённый алгоритм эквивалентен прибавлению единицы к битовому вектору.
 +
=== Пример работы ===
 +
{| class="wikitable" border = 1
 +
|0||1||0||1||style="background:#FFCC00"|1||исходный битовый вектор
 +
|-
 +
| || || || ||^|| начинаем идти с конца
 +
|-
 +
|0||1||0||style="background:#FFCC00"|0||style="background:#FFCC00"|0|| пока элементы равны 1, заменяем их на 0
 +
|-
 +
|0||1||style="background:#FFCC00"|1||0||0|| меняем первый не удовлетворяющий условию цикла элемент на 1
 +
|-
 +
|'''0'''||'''1'''||'''1'''||'''0'''||'''0'''||следующий битовый вектор
 +
|}
  
Двигаясь с конца массива сравниваем соседние элементы, если a[i - 1] > a[i] двигаемся дальше, если a[i - 1] < a[i], m := i - 1(поскольку мы нашли m дальше не смысла двигаться) выходим из цикла.
+
== Специализация алгоритма для генерации следующей перестановки ==
k := i, такое что a[i] > a[m] и a[i] = min(a[i]), при i > m.
+
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
Меняем местами a[m] и a[k] местами.
+
* Меняем его с минимальным элементом, большим нашего, стоящим правее
Осталось упорядочить по возрастанию элементы, стоящие справа от нового m-го элемента, но т.к. они упорядочены по убыванию, достаточно их обернуть.
+
* Перевернем правую часть
----
 
  
== Перебор перестановок методом рекурсии ==
+
'''int[]''' nextPermutation('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина перестановки</font>
 +
  '''for''' i = n - 2 '''downto''' 0
 +
    '''if''' a[i] < a[i + 1]
 +
      min = i + 1;
 +
      '''for''' j = i + 1 '''to''' n - 1
 +
        '''if''' (a[j] < a[min]) '''and''' (a[j] > a[i])
 +
          min = j
 +
      swap(a[i], a[min])
 +
      reverse(a, i + 1, n - 1)
 +
      '''return''' a
 +
  '''return''' ''null''
  
 +
=== Пример работы ===
 +
{| class="wikitable" border = 1
 +
|1||3||style="background:#FFCC00"|2||5||style="background:#FFCC00"|4||исходная перестановка
 +
|-
 +
| || ||^|| || ||находим элемент, нарушающий убывающую последовательность
 +
|-
 +
| || || || ||^||минимальный элемент больше нашего
 +
|-
 +
|1||3||style="background:#FFCC00"|4||5||style="background:#FFCC00"|2||меняем их местами
 +
|-
 +
|1||3||4||style="background:#FFCC00"|2||style="background:#FFCC00"|5||разворачивам правую часть
 +
|-
 +
|'''1'''||'''3'''||'''4'''||'''2'''||'''5'''||следующая перестановка
 +
|}
  
Для того, чтобы построить все перестановки для n элементов, построим все перестановки для n-1 элементов и добавим к каждой из них n-ый элемент всеми возможными n способами.
+
== Специализация алгоритма для генерации следующей мультиперестановки ==
'''Пример''' К перестановке 2431 элемент 5 добавим следующими способами: 24315, 24351, 24531, 25431, 52431.
+
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример).
Для построения следующей перестановки подвинется 4, после чего снова будет двигаться 5. На протяжении всего процесса хранится информация о том, в каком направлении двигается каждый элемент.
+
* Меняем его с минимальным элементом, большим нашего, стоящим правее.
 +
* Переворачиваем правую часть.
 +
'''int[]''' nextMultiperm('''int[]''' b):  <font color=green>// <tex>n</tex> {{---}} длина мультиперестановки</font>
 +
    i = n - 2
 +
    '''while''' (i >= 0) '''and''' (b[i] >= b[i + 1])
 +
      i--
 +
    '''if''' i >= 0
 +
      j = i + 1
 +
      '''while''' (j < n - 1) '''and''' (b[j + 1] > b[i])
 +
        j++
 +
      swap(b[i] , b[j])
 +
      reverse(b, i + 1, n - 1)
 +
      '''return''' b
 +
    '''else'''
 +
      '''return''' ''null''
  
При построении следующей перестановки на первом шаге рассматривается наибольший элемент . Если в направлении его движения еще есть, куда двигаться, передвигаем на одну позицию, это и будет следующей перестановкой. Если двигаться больше некуда (элемент стоит на краю массива и направление его движения — к краю), то меняем его направление движения, после чего «забываем» про этот элемент и строим следующую перестановку для оставшейся части массива, для этого находим в ней наибольший элемент и т.д. (повторяем все снова).
+
=== Пример работы ===
 +
{| class="wikitable" border = 1
 +
|1||2||3||1||style="background:#FFCC00"|2||style="background:#FFCC00"|3||Исходная перестановка.
 +
|-
 +
| || || || ||^|| ||Находим элемент, нарушающий убывающую последовательность.
 +
|-
 +
| || || || || ||^||Минимальный элемент больше нашего.
 +
|-
 +
|1||2||3||1||style="background:#FFCC00"|3||style="background:#FFCC00"|2||Меняем их местами.
 +
|-
 +
|'''1'''||'''2'''||'''3'''||'''1'''||'''3'''||'''2'''||Следующая мультиперестановка.
 +
|}
  
 +
== Специализация алгоритма для генерации следующего сочетания ==
  
----
+
* Добавим в конец массива с сочетанием <tex>N+1</tex> – максимальный элемент.
 +
* Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на <tex>2</tex> и больше.
 +
* Увеличим найденный элемент на <tex>1</tex>, и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание.
 +
'''int[]''' nextChoose('''int[]''' a, '''int''' n, '''int''' k): <font color=green>// <tex>n,k </tex> {{---}} параметры сочетания</font>
 +
  '''for''' i = 0 '''to''' k - 1
 +
    b[i] = a[i]
 +
  b[k] = n + 1
 +
  i = k - 1
 +
  '''while''' (i >= 0) '''and''' (b[i + 1] - b[i] < 2)
 +
    i--
 +
  '''if''' i >= 0
 +
      b[i]++
 +
      '''for''' j = i + 1 '''to''' k - 1
 +
        b[j] = b[j - 1] + 1
 +
      '''for''' i = 0 '''to''' k - 1
 +
        a[i] = b[i]
 +
      '''return''' a
 +
  '''else'''
 +
    '''return''' ''null''
  
== Ссылки ==
+
=== Пример работы ===
[http://rain.ifmo.ru/cat/view.php/vis/combinations/permutations-2000 Дискретная математика : алгоритмы]
+
{| class="wikitable" border = 1
 +
|1||2||5||6||style="background:#FFCC00"|'''7'''||Дописываем 7 в конец сочетания.
 +
|-
 +
|1||style="background:#FFCC00"|2||5||6||'''7'''||
 +
|-
 +
| ||^|| || || ||Находим элемент i, a[i + 1] - a[ i ] >= 2
 +
|-
 +
|1||style="background:#FFCC00"|3||5||6||'''7'''||Увеличиваем его на 1.
 +
|-
 +
|1||3||style="background:#FFCC00"|4||style="background:#FFCC00"|5||style="background:#FFCC00"|'''6'''||Дописываем минимальный хвост.
 +
|-
 +
|'''1'''||'''3'''||'''4'''||'''5'''||''' '''||Следующее сочетание.
 +
|}
  
[http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0 Википедия - свободная энциклопедия]
+
== Специализация алгоритма для генерации следующего разбиения на слагаемые ==
 +
Рассматриваемый алгоритм находит следующее [[комбинаторные объекты|разбиение на слагаемые]], при этом разбиение упорядоченно по возрастанию.
 +
* Увеличим предпоследнее слагаемое на <tex>1</tex>, уменьшим последнее слагаемое на <tex>1</tex>.
 +
** Если предпоследнее слагаемое стало больше последнего, то увеличиваем предпоследнее слагаемое на величину последнего.
 +
** Если предпоследнее слагаемое умноженное на 2 меньше последнего, то разбиваем последнее слагаемое <tex>s</tex> на два слагаемых <tex>a</tex> и <tex>b</tex> таких, что <tex>a</tex> равно предпоследнему слагаемому, а <tex>b = s - a</tex>. Повторяем этот процесс, пока разбиение остается корректным, то есть предпоследнее слагаемое хотя бы в два раза меньше последнего.
 +
 
 +
<code>
 +
<font color=green>// <tex>b</tex> {{---}} список, содержащий разбиение данного числа <tex>b.size</tex>{{---}} его размер </font>
 +
'''list<int>'''  nextPartition('''list<int>''' b):
 +
    b[b.size - 1]--
 +
    b[b.size - 2]++
 +
    '''if''' b[b.size - 2] > b[b.size - 1]
 +
      b[b.size - 2] += b[b.size - 1]
 +
      b.remove(b.size - 1)
 +
    '''else'''
 +
      '''while''' b[b.size - 2] * 2 <= b[b.size - 1]
 +
        b.add(b[b.size - 1] - b[b.size - 2])
 +
        b[b.size - 2] = b[b.size - 3]
 +
    '''return''' b
 +
</code>
 +
 
 +
=== Пример работы ===
 +
{| class="wikitable" border = 1
 +
|1||style="background:#FFCC00"|1||style="background:#FFCC00"|7|| || ||Прибавим 1 + 1, вычтем 7 - 1.
 +
|-
 +
|1||style="background:#FFCC00"|2||style="background:#FFCC00"|6|| || ||Проверяем: 2 < 6, значит разбиваем 6 пока оно не станет меньше 4
 +
|-
 +
|1||2||style="background:#FFCC00"|2||style="background:#FFCC00"|4|| ||
 +
|-
 +
|1||2||2||style="background:#FFCC00"|2||style="background:#FFCC00"|2||
 +
|-
 +
|'''1'''||'''2'''||'''2'''||'''2'''||'''2'''||Следующее разбиение на слагаемые числа 9.
 +
|}
 +
 
 +
{| class="wikitable" border = 1
 +
|1||style="background:#FFCC00"|4||style="background:#FFCC00"|5||Прибавим 4 + 1, вычтем 5 - 1.
 +
|-
 +
|1||style="background:#FFCC00"|5||style="background:#FFCC00"|4||Проверяем: 5 > 4, значит прибавим к 5 + 4.
 +
|-
 +
|1||9||style="background:#FFCC00"|4||Удалим последний элемент.
 +
|-
 +
|'''1'''||'''9'''||||Следующее разбиение на слагаемые числа 10.
 +
|}
 +
 
 +
== Специализация алгоритма для генерации следующего разбиения на подмножества ==
 +
 
 +
Рассмотрим множество первых n натуральных чисел:<tex>N_n = \{1, 2, ..., n\}</tex>
 +
 
 +
Упорядочим все разбиения на множества <tex>N_n</tex> лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество <tex> A \subset N_n </tex> лексикографически меньше подмножества <tex> B \subset N_n </tex> , если верно одно из следующих условий:
 +
 
 +
*существует <tex>i</tex> такое, что <tex>i \in A</tex> , <tex>i \notin B</tex>, для всех <tex>j < i: j \in A</tex> если и только если <tex>j \in B</tex> , и существует <tex>k > i</tex> такое что <tex>k \in B</tex>;
 +
* <tex> A \subset B </tex> и <tex>i < j</tex> для всех <tex>i \in A</tex> и <tex>j \in B</tex> \ <tex> A </tex>.
 +
 
 +
Разбиения упорядочены лексикографически следующим образом. Разбиение <tex>N_n = A_1 \cup A_2 \cup . . . \cup A_k</tex> лексикографически меньше разбиения <tex>N_n = 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> \{1, 2, 3\}~ \{4, 5\}</tex> будет выглядеть так:
 +
 
 +
{| class="wikitable" border = 1
 +
|1||2||3
 +
|-
 +
|4||5||
 +
|}
 +
 
 +
* Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не сможем выполнить одно из действий, описанных ниже:
 +
** Заменить рассматриваемый элемент уже удаленным. Из всех подходящих элементов выбираем минимальный. '''Важное замечание''': мы не можем заменить первый элемент подмножества, мы можем только удалить его.
 +
** Дополнить рассматриваемое подмножество уже удаленным элементом. Из всех подходящих элементов выбираем минимальный.
 +
* Допишем лексикографически минимальный хвост подмножеств из оставшихся элементов.
 +
 
 +
<code>
 +
'''list<list<int>>''' nextSetPartition('''list<list<int>>''' a):
 +
  <font color=green>// <tex>a</tex> {{---}} список, содержащий подмножества</font>
 +
  <font color=green>// <tex>used</tex> {{---}} список, в котором мы храним удаленные элементы</font>
 +
  used = '''list<int>'''
 +
  fl = ''false''
 +
  '''for''' i = a.size - 1 '''downto''' 0
 +
      '''if''' (used.size != 0) '''and''' (used[used.size - 1] > a[i][a[i].size - 1])  <font color=green>// если можем добавить в конец подмножества элемент из <tex>used</tex></font>
 +
          a[i].add(used[used.size - 1])  <font color=green>//добавляем</font>
 +
          used.remove(used.size - 1)
 +
          '''break'''
 +
      '''for''' j = a[i].size - 1 '''downto''' 0
 +
          '''if''' (used.size != 0) '''and''' (j != 0) '''and''' (used[used.size - 1] > a[i][j])    <font color=green>//если можем заменить элемент, другим элементом из списка <tex>used</tex> </font>
 +
            a[i][j] = used[used.size - 1]  <font color=green>//заменяем</font>
 +
            fl = ''true''
 +
            '''break'''
 +
      '''if''' fl '''break'''
 +
      used.add(a[i][j])  <font color=green>//добавляем в <tex>used</tex> <tex>j</tex> элемент <tex>i</tex>-го подмножества</font>
 +
      a[i].remove(j)  <font color=green>//удаляем <tex>j</tex> элемент <tex>i</tex>-го подмножества</font>
 +
  <font color=green>//далее выведем все получившиеся подмножества</font>
 +
  sort(used)
 +
  '''for''' i = 0 '''to''' used.size - 1
 +
    a.add('''list<int>'''(used[i]))  <font color=green>//добавляем лексикографически минимальных хвост</font>
 +
  '''return''' a
 +
</code>
 +
 
 +
=== Пример работы ===
 +
 
 +
'''Рассмотрим следующее разбиение:'''
 +
 
 +
{| class="wikitable" border = 1
 +
|1||2||3
 +
|-
 +
|4||5||
 +
|}
 +
 
 +
'''1 Шаг:'''
 +
 
 +
{| class="wikitable" border = 1
 +
|1||2||3||
 +
|-
 +
|4||style="background:#FFCC00"|5||||
 +
|-
 +
| ||^|| ||Удалили элемент 5.
 +
|-
 +
| || || ||used
 +
|}
 +
 
 +
 
 +
'''2 Шаг:'''
 +
 
 +
{| class="wikitable" border = 1
 +
|1||2||3||
 +
|-
 +
|style="background:#FFCC00"|4|| ||||
 +
|-
 +
|^|| || ||Удалили элемент 4. Так как он является первым в подмножестве, то мы не можем заменить его на другой.
 +
|-
 +
|5|| || ||used
 +
|}
 +
 
 +
 
 +
'''3 Шаг:'''
 +
 
 +
{| class="wikitable" border = 1
 +
|1||2||3||style="background:#FFCC00"|4||
 +
|-
 +
| || || ||^||Дополнили первое подмножество элементом 4
 +
|-
 +
|5|| || || ||used
 +
|} 
 +
 
 +
 
 +
'''4 Шаг:'''
 +
   
 +
{| class="wikitable" border = 1
 +
|1||2||3||4||
 +
|-
 +
|style="background:#FFCC00"|5|| || || ||Дописали лексикографически минимальный хвост
 +
|-
 +
| || || || ||used
 +
|}
 +
 
 +
== См.также ==
 +
* [[Получение предыдущего объекта]]
 +
* [[Получение объекта по номеру]]
 +
* [[Получение номера по объекту]]
 +
 
 +
== Источники информации ==
 +
 
 +
* [http://rain.ifmo.ru/cat/view.php/vis/combinations/permutations-2000 Визуализатор перестановок]
 +
* [http://cppalgo.blogspot.com/2011/02/episode-2.html Пример компактного кода для перестановок (С++)]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Комбинаторика]]

Текущая версия на 01:25, 16 декабря 2017

Алгоритм[править]

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

Объект [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]0[/math], его можно увеличить, не меняя оставшейся части
  • Вместо [math]0[/math] записываем [math]1[/math]
  • Дописываем минимально возможный хвост из нулей
int[] nextVector(int[] a): // [math]n[/math] — длина вектора
  while (n >= 0) and (a[n] != 0)
      a[n] = 0
      n--
  if n == -1
    return null
  a[n] = 1
  return a

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

Пример работы[править]

0 1 0 1 1 исходный битовый вектор
^ начинаем идти с конца
0 1 0 0 0 пока элементы равны 1, заменяем их на 0
0 1 1 0 0 меняем первый не удовлетворяющий условию цикла элемент на 1
0 1 1 0 0 следующий битовый вектор

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

  • Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
  • Меняем его с минимальным элементом, большим нашего, стоящим правее
  • Перевернем правую часть
int[] nextPermutation(int[] a): // [math]n[/math] — длина перестановки
  for i = n - 2 downto 0
    if a[i] < a[i + 1]
      min = i + 1;
      for j = i + 1 to n - 1
        if (a[j] < a[min]) and (a[j] > a[i])
          min = j
      swap(a[i], a[min])
      reverse(a, i + 1, n - 1)
      return a
  return null 

Пример работы[править]

1 3 2 5 4 исходная перестановка
^ находим элемент, нарушающий убывающую последовательность
^ минимальный элемент больше нашего
1 3 4 5 2 меняем их местами
1 3 4 2 5 разворачивам правую часть
1 3 4 2 5 следующая перестановка

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

  • Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример).
  • Меняем его с минимальным элементом, большим нашего, стоящим правее.
  • Переворачиваем правую часть.
int[] nextMultiperm(int[] b):  // [math]n[/math] — длина мультиперестановки
    i = n - 2
    while (i >= 0) and (b[i] >= b[i + 1]) 
      i--
    if i >= 0 
      j = i + 1
      while (j < n - 1) and (b[j + 1] > b[i]) 
        j++
      swap(b[i] , b[j])
      reverse(b, i + 1, n - 1)
      return b
    else
      return null

Пример работы[править]

1 2 3 1 2 3 Исходная перестановка.
^ Находим элемент, нарушающий убывающую последовательность.
^ Минимальный элемент больше нашего.
1 2 3 1 3 2 Меняем их местами.
1 2 3 1 3 2 Следующая мультиперестановка.

Специализация алгоритма для генерации следующего сочетания[править]

  • Добавим в конец массива с сочетанием [math]N+1[/math] – максимальный элемент.
  • Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на [math]2[/math] и больше.
  • Увеличим найденный элемент на [math]1[/math], и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание.
int[] nextChoose(int[] a, int n, int k): // [math]n,k [/math] — параметры сочетания
  for i = 0 to k - 1 
    b[i] = a[i]
  b[k] = n + 1
  i = k - 1
  while (i >= 0) and (b[i + 1] - b[i] < 2) 
    i--
  if i >= 0 
     b[i]++
     for j = i + 1 to k - 1 
       b[j] = b[j - 1] + 1
     for i = 0 to k - 1 
       a[i] = b[i]
     return a
  else
    return null

Пример работы[править]

1 2 5 6 7 Дописываем 7 в конец сочетания.
1 2 5 6 7
^ Находим элемент i, a[i + 1] - a[ i ] >= 2
1 3 5 6 7 Увеличиваем его на 1.
1 3 4 5 6 Дописываем минимальный хвост.
1 3 4 5 Следующее сочетание.

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

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

  • Увеличим предпоследнее слагаемое на [math]1[/math], уменьшим последнее слагаемое на [math]1[/math].
    • Если предпоследнее слагаемое стало больше последнего, то увеличиваем предпоследнее слагаемое на величину последнего.
    • Если предпоследнее слагаемое умноженное на 2 меньше последнего, то разбиваем последнее слагаемое [math]s[/math] на два слагаемых [math]a[/math] и [math]b[/math] таких, что [math]a[/math] равно предпоследнему слагаемому, а [math]b = s - a[/math]. Повторяем этот процесс, пока разбиение остается корректным, то есть предпоследнее слагаемое хотя бы в два раза меньше последнего.

// [math]b[/math] — список, содержащий разбиение данного числа [math]b.size[/math]— его размер 
list<int>  nextPartition(list<int> b): 
   b[b.size - 1]--
   b[b.size - 2]++
   if b[b.size - 2] > b[b.size - 1] 
      b[b.size - 2] += b[b.size - 1]
      b.remove(b.size - 1)
   else
     while b[b.size - 2] * 2 <= b[b.size - 1] 
       b.add(b[b.size - 1] - b[b.size - 2])
       b[b.size - 2] = b[b.size - 3]
   return b

Пример работы[править]

1 1 7 Прибавим 1 + 1, вычтем 7 - 1.
1 2 6 Проверяем: 2 < 6, значит разбиваем 6 пока оно не станет меньше 4
1 2 2 4
1 2 2 2 2
1 2 2 2 2 Следующее разбиение на слагаемые числа 9.
1 4 5 Прибавим 4 + 1, вычтем 5 - 1.
1 5 4 Проверяем: 5 > 4, значит прибавим к 5 + 4.
1 9 4 Удалим последний элемент.
1 9 Следующее разбиение на слагаемые числа 10.

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

Рассмотрим множество первых n натуральных чисел:[math]N_n = \{1, 2, ..., n\}[/math]

Упорядочим все разбиения на множества [math]N_n[/math] лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество [math] A \subset N_n [/math] лексикографически меньше подмножества [math] B \subset N_n [/math] , если верно одно из следующих условий:

  • существует [math]i[/math] такое, что [math]i \in A[/math] , [math]i \notin B[/math], для всех [math]j \lt i: j \in A[/math] если и только если [math]j \in B[/math] , и существует [math]k \gt i[/math] такое что [math]k \in B[/math];
  • [math] A \subset B [/math] и [math]i \lt j[/math] для всех [math]i \in A[/math] и [math]j \in B[/math] \ [math] A [/math].

Разбиения упорядочены лексикографически следующим образом. Разбиение [math]N_n = A_1 \cup A_2 \cup . . . \cup A_k[/math] лексикографически меньше разбиения [math]N_n = 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] \{1, 2, 3\}~ \{4, 5\}[/math] будет выглядеть так:
1 2 3
4 5
  • Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не сможем выполнить одно из действий, описанных ниже:
    • Заменить рассматриваемый элемент уже удаленным. Из всех подходящих элементов выбираем минимальный. Важное замечание: мы не можем заменить первый элемент подмножества, мы можем только удалить его.
    • Дополнить рассматриваемое подмножество уже удаленным элементом. Из всех подходящих элементов выбираем минимальный.
  • Допишем лексикографически минимальный хвост подмножеств из оставшихся элементов.

list<list<int>> nextSetPartition(list<list<int>> a):
 // [math]a[/math] — список, содержащий подмножества
 // [math]used[/math] — список, в котором мы храним удаленные элементы
 used = list<int>
 fl = false
 for i = a.size - 1 downto 0
     if (used.size != 0) and (used[used.size - 1] > a[i][a[i].size - 1])   // если можем добавить в конец подмножества элемент из [math]used[/math]
         a[i].add(used[used.size - 1])   //добавляем
         used.remove(used.size - 1)
         break
     for j = a[i].size - 1 downto 0
         if (used.size != 0) and (j != 0) and (used[used.size - 1] > a[i][j])    //если можем заменить элемент, другим элементом из списка [math]used[/math] 
            a[i][j] = used[used.size - 1]   //заменяем
            fl = true
            break
     if fl break
     used.add(a[i][j])   //добавляем в [math]used[/math] [math]j[/math] элемент [math]i[/math]-го подмножества 
     a[i].remove(j)   //удаляем [math]j[/math] элемент [math]i[/math]-го подмножества
 //далее выведем все получившиеся подмножества
 sort(used)
 for i = 0 to used.size - 1
    a.add(list<int>(used[i]))   //добавляем лексикографически минимальных хвост
 return a

Пример работы[править]

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

1 2 3
4 5

1 Шаг:

1 2 3
4 5
^ Удалили элемент 5.
used


2 Шаг:

1 2 3
4
^ Удалили элемент 4. Так как он является первым в подмножестве, то мы не можем заменить его на другой.
5 used


3 Шаг:

1 2 3 4
^ Дополнили первое подмножество элементом 4
5 used


4 Шаг:

1 2 3 4
5 Дописали лексикографически минимальный хвост
used

См.также[править]

Источники информации[править]