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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Специализация алгоритма для генерации предыдущего разбиения на множества)
Строка 126: Строка 126:
  
 
==Специализация алгоритма для генерации предыдущего разбиения на множества==
 
==Специализация алгоритма для генерации предыдущего разбиения на множества==
 +
Рассматриваемый алгоритм находит предыдущее [[комбинаторные объекты|разбиение на множества]].
 +
 +
Разбиения упорядочены по возрастанию мощностей  наибольших множеств данного разбиения, а внутри разбиений множества упорядочены по убыванию мощностей.
 +
 +
Пример упорядоченного списка разбиений множества из <tex> 6</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> 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> элемента)
 +
 +
 +
Псевдокод
 +
'''vector<int>b''' PreviousSetPartition(vector<int>a)
 +
  '''for''' int i = a.size - 1 '''to''' 0
 +
  '''if''' a[i] > 1
 +
    '''if''' i > 0                    <font color = green> // см 2 пункт алгоритма (a[0] - наибольшее множество)</font>
 +
      a[i] --
 +
      '''if'''  i + 1 < a.size        <font color = green> // если есть еще элементы кроме a[0] </font>
 +
        a[i + 1] ++
 +
      '''else''' a.push_back(1)
 +
    '''else''' int sum = a[0]
 +
     
 +
      '''while''' i < a.size - 1
 +
      i++
 +
        sum += a[i]
 +
      '''while''' a[a.size] != a[0]
 +
        a.pop_back
 +
      '''while''' sum > b[1]
 +
        sum -= a[0]
 +
        a.push(a[0])                    <font color = green> // см 2 пункт алгоритма, необходимо забить вектор элементами, мощность которых <= a[0] </font>
 +
      '''if''' sum != 0
 +
      a.push(sum);
 +
  return a
  
 
== См. также ==
 
== См. также ==

Версия 23:25, 22 января 2016

Алгоритм

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

Объект [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[j])
      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] 6[/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] 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] элемента)


Псевдокод

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

См. также

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