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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Специализация алгоритма для генерации предыдущего битового вектора)
(Специализация алгоритма для генерации предыдущего битового вектора)
Строка 22: Строка 22:
 
     '''return''' a
 
     '''return''' a
 
Приведённый алгоритм эквивалентен вычитанию единицы из битового вектора.
 
Приведённый алгоритм эквивалентен вычитанию единицы из битового вектора.
 +
== Специализация алгоритма для генерации предыдущей перестановки ==
 +
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность
 +
* Меняем его с максимальным элементом, меньшим нашего, стоящим правее
 +
* Перевернем правую часть
 +
 +
'''int[]''' nextPermutation('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина перестановки</font>
 +
  '''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''

Версия 11:11, 30 декабря 2014

Алгоритм

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

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

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

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

  • Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность
  • Меняем его с максимальным элементом, меньшим нашего, стоящим правее
  • Перевернем правую часть
int[] nextPermutation(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