Получение предыдущего объекта

Алгоритм

Определение:

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

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

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

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

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

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

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

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

Реализация

int[] prevVector(int[] a): // $n$ — длина вектора
  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): // $n$ — длина перестановки
  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

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

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

Алгоритм полностью аналогичен генерации предыдущей перестановки

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

int[] prevMultipermutation(int[] a): // $n$ — длина перестановки
  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

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

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

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

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

Пример:

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

Реализация

int[] prevChoose(int[] a): // $n$ — количество различных элементов
  a[0] = 0                       // $k$ — длина сочетания
  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

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

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

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

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

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

Пример:

Случай 1.

Случай 2.

Реализация

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

list<int> prevPartition(list<int> a): 
  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();

См. также

• Получение объекта по номеру
• Получение номера по объекту
• Получение следующего объекта