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

Алгоритм

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

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

Объект [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[max])
      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]A = A_1 \cup A_2 \cup . . . \cup A_k[/math] лексикографически меньше разбиения [math]B = B_1 \cup B_2 \cup . . . \cup B_l[/math] если существует такое [math]i[/math], что [math]A_1 = B_1, A_2 = B_2, . . . ,A_{i - 1} = B_{i - 1}, A_i \lt B_i[/math].

Пример упорядоченного списка разбиений множества из [math] 6[/math] элементов:

[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]

Рассмотрим алгоритм нахождения лексикографически предыдущего разбиения на подмножества:

• Будем хранить подмножества в списке , например, разбиение [math] \{3, 1, 1, 1\}[/math] будет выглядеть так:

3

1

1

1

Будем идти справа налево и применять следующий алгоритм:

• Найдём множество [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] элемента)

Реализация

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

Пример работы

Рассмотрим следующее разбиение:

3

1

1 Шаг:

3	1
^		3 — наименьший элемент, от которого мы можем отнять 1, однако 3 также является первым элементом, значит предыдущее разбиение должно состоять из элементов [math]\le 2 [/math].

2 Шаг:

2	1
	^	уменьшили 3 на 1, прошли до конца списка, вычислили сумму оставшихся элементов, которую теперь надо распределить на элементы [math]\le 2 [/math]
1	1	sum

3 Шаг:

2
^		удалили все элементы кроме первого

4 Шаг:

2	2
	^	распределили сумму

См. также

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

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

• Визуализатор перестановок
• Orderings of partitions