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

Материал из Викиконспекты
Версия от 21:02, 19 декабря 2012; Korektur (обсуждение | вклад) (Специализация алгоритма для генерации следующего разбиения на подмножества)
Перейти к: навигация, поиск

Алгоритм

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

Объект [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(так как он минимальный из всех элементов, которыми мы могли его дополнить), и дописали лексикографически минимальный хвост.

Ссылки