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

Алгоритм

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

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

Объект [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] — минимально возможный.

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

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

for i = n downto 1
    if a[i] == 0
        a[i] = 1
        for j = i + 1 to n
            a[j] = 0
        break

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

0	1	0	1	1	исходный битовый вектор
		^			находим элемент 0 (самый правый)
0	1	1	1	1	меняем его на 1
0	1	1	0	0	меняем элементы правее на нули
0	1	1	0	0	следующий битовый вектор

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

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

for i = n - 1 downto 1
    if a[i] < a[i + 1]
        // a[j] = min {a[j] > a[i], где j > i}
        swap(a[i], a[j])
        reverse(a[i + 1] .. a[n])
        break

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

1	3	2	5	4	исходная перестановка
		^			находим элемент, нарушающий убывающую последовательность
				^	минимальный элемент больше нашего
1	3	4	5	2	меняем их местами
1	3	4	2	5	разворачивам правую часть
1	3	4	2	5	следующая перестановка

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

• Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не выполнится одно из условий ниже:

1) Каждый раз, рассматривая новый элемент, будем пытаться заменить его уже удаленным элементом из нашего массива, так чтобы не нарушалась возрастающая последовательность элементов в этом подмножестве. Из всех подходящих элементов выбираем минимальный. Важное замечание: мы не можем заменить 1ый элемент подмножества, мы можем только удалить его.

2) Каждый раз, переходя в новое подмножество, будем пытаться дополнить его элементом из уже удаленных, так чтобы не нарушалась возрастающая последовательность элементов в этом подмножестве. Из всех подходящих элементов выбираем минимальный.

• Допишем лексикографически минимальный хвост подмножеств из оставшихся элементов.

// a - матрица содержащая подмножества
// used - массив в котором мы храним, удаленные элементы
for i = n - 1 downto 0  //перебираем все подмножества, начиная с последнего
    if ( /*можем добавить в конец подмножества элемент из used*/ ){
        // добавляем
        break;
    }
    for j = m - 1 downto 0  // перебираем все элементы текущего подмножества
        if( /* можем заменить элемент, другим элементом из массива used*/ ){
           //заменяем
           break;
        }
        used.add(a[i][j]); //удаляем элемент и добавляем его в массив
printsets();               //далее выведем все получившиеся подмножества
sort(used);                //отсортируем массив оставшихся элементов
for i = 0 to used.size() do
   println(used[i]);     //выведем лексикографически минимальный хвост

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

Рассмотрим следующее разбиение: {1, 2, 3} {4, 5}

1 Шаг: {1, 2, 3} {4} used = {5};

Удалили элемент 5.

2 Шаг: {1, 2, 3} used = {4, 5};

Удалили элемент 4. Так как он является первым в подмножестве, то мы не можем заменить его на другой.

3 Шаг: {1, 2, 3, 4} {5} used = {};

Дополнили первое подмножество элементом 4(так как он минимальный из всех элементов, которыми мы могли его дополнить), и дописали лексикографически минимальный хвост.

Ссылки

• Получение объекта по номеру
• Получение номера по объекту
• Визуализатор перестановок
• Пример компактного кода для перестановок (С++)