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

Алгоритм

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

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

Объект [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

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

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

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

int[] prevMultipermutation(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]t[/math] не существует, значит было дано первое сочетание. А значит и предыдущего сочетания не существует.

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

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