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

Алгоритм

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

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

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

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