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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Специализация алгоритма для генерации предыдущего разбиения на слагаемые)
м (rollbackEdits.php mass rollback)
 
(не показаны 24 промежуточные версии 6 участников)
Строка 11: Строка 11:
  
 
== Специализация алгоритма для генерации предыдущего битового вектора ==
 
== Специализация алгоритма для генерации предыдущего битового вектора ==
[[Файл: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|искомый суффикс, преобразование]]
 +
|}
 
===Реализация===
 
===Реализация===
  
Строка 38: Строка 37:
  
 
'''Пример:'''
 
'''Пример:'''
[[Файл:Prevperm.png|600px|thumb|left|искомый суффикс (убывающая последовательность), элемент нарушающий последовательность, преобразование]]
+
{| 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>
Строка 55: Строка 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''
 +
 
===Мультиперестановка===
 
===Мультиперестановка===
 
Если данный алгоритм применить к мультиперестановке, то он выведет корректный результат, то есть предыдущую мультиперестановку.
 
Если данный алгоритм применить к мультиперестановке, то он выведет корректный результат, то есть предыдущую мультиперестановку.
Строка 67: Строка 59:
  
  
* Проходя справа налево, находим элемент <tex>t</tex> так, чтобы его разница со следующим отличалась более чем на единицу (пусть элемент с индексом <tex>0</tex> равен <tex>0</tex>, а первый элемент хранится в <tex>1</tex>)
+
* Проходя справа налево, находим элемент <tex>t</tex> так, чтобы его разница со следующим отличалась более чем на единицу (пусть элемент с индексом <tex>0</tex> равен <tex>0</tex>, а первый элемент хранится в <tex>a[1]</tex>)
 
* уменьшаем его на единицу
 
* уменьшаем его на единицу
 
* дописываем максимально возможный хвост
 
* дописываем максимально возможный хвост
Строка 89: Строка 81:
 
         t++
 
         t++
 
       '''return''' a
 
       '''return''' a
   '''return''' null
+
   '''return''' ''null''
  
 
== Специализация алгоритма для генерации предыдущего разбиения на слагаемые ==
 
== Специализация алгоритма для генерации предыдущего разбиения на слагаемые ==
Строка 102: Строка 94:
 
'''Пример:'''  
 
'''Пример:'''  
  
Случай 1.
+
Первый случай:
 
{| cellpadding="3" style="margin-left: left; margin-right: left;"
 
{| cellpadding="3" style="margin-left: left; margin-right: left;"
 
| [[Файл:Prevpart1.png|600px|thumb|2 < 9 / 2, значит разделим 9 на два слагаемых, 4 и 5]]  
 
| [[Файл:Prevpart1.png|600px|thumb|2 < 9 / 2, значит разделим 9 на два слагаемых, 4 и 5]]  
 
|}
 
|}
Случай 2.
+
Второй случай:
 
{| cellpadding="3" style="margin-left: left; margin-right: left;"
 
{| cellpadding="3" style="margin-left: left; margin-right: left;"
 
| [[Файл:Prevpart2.png|600px|thumb|1 + 2 - наибольший префикс, который можно не изменять, уменьшаем первую 3, дописываем наибольший хвост - 9 ]]  
 
| [[Файл:Prevpart2.png|600px|thumb|1 + 2 - наибольший префикс, который можно не изменять, уменьшаем первую 3, дописываем наибольший хвост - 9 ]]  
Строка 124: Строка 116:
 
     '''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]--
Строка 132: Строка 124:
 
       '''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
 +
 
 +
'''Пример работы'''
 +
 
 +
Рассмотрим следующее разбиение:
 +
{| 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 Шаг:'''
 +
 
 +
{| class="wikitable" border = 1
 +
|2||style="background:#FFCC00"|2
 +
|-
 +
| ||^||распределили сумму
 +
|}
  
 
== См. также ==
 
== См. также ==
Строка 138: Строка 213:
 
* [[Получение номера по объекту]]
 
* [[Получение номера по объекту]]
 
* [[Получение следующего объекта]]
 
* [[Получение следующего объекта]]
 +
== Источники информации ==
 +
 +
* [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
^ распределили сумму

См. также

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