Получение следующего объекта
Версия от 22:50, 16 декабря 2013; Mogikan (обсуждение | вклад)
Алгоритм
| Определение: |
| Получение следующего объекта — это нахождение объекта, следующего за данным в лексикографическом порядке. |
Объект называется следующим за , если и не найдется такого , что .
Отсюда понятен алгоритм:
- Находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта
- К оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило )
- Дописываем минимальный возможный хвост
По построению получаем, что — минимально возможный.
Специализация алгоритма для генерации следующего битового вектора
- Находим минимальный суффикс, в котором есть 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 | следующая перестановка |
Специализация алгоритма для генерации следующей мультиперестановки
- Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример).
- Меняем его с минимальным элементом, большим нашего, стоящим правее.
- Переворачиваем правую часть.
function nextMultiperm(var b:array[1..N] of integer):mutiperm;
var i , j : integer;
begin
i := N - 1;
while (i > 0) and (b[i] >= b[i + 1]) do
dec(i);
if i > 0 then
begin
j := i + 1;
while (j < N) and (b[j + 1] > b[i]) do
inc(j);
swap(b[i] , b[j]);
for j := i + 1 to (N + i) div 2 do
swap(b[j], b[N - j + i + 1]);
nextMultiperm:=b[1..N];
end
else
begin
nextMultiperm:=null;
end;
end;
Пример работы
| 1 | 2 | 3 | 1 | 2 | 3 | Исходная перестановка. |
| ^ | Находим элемент, нарушающий убывающую последовательность. | |||||
| ^ | Минимальный элемент больше нашего. | |||||
| 1 | 2 | 3 | 1 | 3 | 2 | Меняем их местами. |
| 1 | 2 | 3 | 1 | 3 | 2 | Следующая мультиперестановка. |
Специализация алгоритма для генерации следующего сочетания
- Добавим в конец массива с сочетанием N+1 – максимальный элемент.
- Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на 2.
- Увеличим найденный элемент на 1, и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание.
function nextChoose(var a:array[1..N+1] of integer):choose; // n,k - параметры сочетания.
var i,j : integer;
begin
a[k + 1] := n + 1;
i := n;
while (i > 0) and ((a[i + 1] - a[i]) < 2) do
i := i - 1;
if i > 0 then
begin
a[i] := a[i] + 1;
for j := i + 1 to k do
a[j] := a[j - 1] + 1;
nextChoose:=a[1..n];
end
else
nextChoose:=null;
end;
Пример работы
| 1 | 2 | 5 | 6 | 7 | Дописываем 7 в конец сочетания. |
| 1 | 2 | 5 | 6 | 7 | |
| ^ | Находим элемент i, a[i + 1] - a[ i ] >= 2 | ||||
| 1 | 3 | 5 | 6 | 7 | Увеличиваем его на 1. |
| 1 | 3 | 4 | 5 | 6 | Дописываем минимальный хвост. |
| 1 | 3 | 4 | 5 | Следующее сочетание. |
Специализация алгоритма для генерации следующего разбиения на слагаемые
- Увеличим предпоследнее число на 1, уменьшим последнее на 1.
- Если предпоследний элемент стал больше последнего, то увеличиваем предпоследний элемент на величину последнего.
- Если предпоследний элемент меньше последнего, то проверяем, можем ли мы разбить последний элемент на сумму предпоследних. Если да – разбиваем, пока предпоследний*2 < последнего.
// Алгоритм работает только для лексикографического порядка.
// b – массив, содержащий разбиение данного числа, length – его размер.
function nextPartition(var b:array[1..length] of integer):partition;
var i : integer;
begin
b[length] := b[length] - 1;
b[length - 1] := b[length - 1] + 1;
if b[length - 1] > b[length] then
begin
b[length - 1] := b[length - 1] + b[length];
length := length - 1;
end
else
begin
i := 0;
while b[length - 1] * 2 <= b[length + i] do
begin
b[length + i + 1] := b[length + i] - b[length - 1];
b[length + i] := b[length - 1];
i := i + 1;
end;
length := length + i;
end;
nextPartition := b[1..length];
end;
Пример работы
| 1 | 1 | 7 | Прибавим 1 + 1, вычтем 7 - 1. | ||
| 1 | 2 | 6 | Проверяем: 2<6, значит разбиваем 6 пока оно не станет <4 | ||
| 1 | 2 | 2 | 4 | ||
| 1 | 2 | 2 | 2 | 2 | |
| 1 | 2 | 2 | 2 | 2 | Следующее разбиение на слагаемые числа 9. |
Специализация алгоритма для генерации следующего разбиения на подмножества
Рассмотрим множество первых n натуральных чисел:
| Определение: |
| Разбиением на множества называется представление множества, как объединения одного или более попарно не пересекающихся подмножеств множеств. Так же разбиения на одинаковые множества, но в разном порядке считаются одинаковыми. |
Например, для существуют следующие разбиения:
и т. д., всего таких разбиений для существует 52.
Упорядочим все разбиения на множества лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество лексикографически меньше подмножества , если верно одно из следующих условий:
- существует такое, что , , для всех если и только если , и существует такое что ;
- и для всех и \ .
Разбиения упорядочены лексикографически следующим образом. Разбиение лексикографически меньше разбиения если существует такое , что .
Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:
- Будем хранить подмножества с помощью двумерного массива, например, разбиение будет выглядеть так:
| 1 | 2 | 3 |
| 4 | 5 |
- Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не сможем выполнить одно из действий, описанных ниже:
- Заменить рассматриваемый элемент уже удаленным. Из всех подходящих элементов выбираем минимальный. Важное замечание: мы не можем заменить 1ый элемент подмножества, мы можем только удалить его.
- Дополнить рассматриваемое подмножество уже удаленным элементом. Из всех подходящих элементов выбираем минимальный.
- Допишем лексикографически минимальный хвост подмножеств из оставшихся элементов.
// a - матрица, содержащая подмножества
// used - массив, в котором мы храним удаленные элементы
fl = false
for i = n - 1 downto 0
if можем добавить в конец подмножества элемент из used
добавляем
break
for j = a[i].size - 1 downto 0
if можем заменить элемент, другим элементом из массива used
заменяем
fl = true
break
used.add(a[i][j]) // удаляем элемент и добавляем его в массив
if (fl) break
// далее выведем все получившиеся подмножества
sort(used)
for i = 0 to used.size - 1
println(used[i]) // выводим лексикографически минимальных хвост
Пример работы
Рассмотрим следующее разбиение:
| 1 | 2 | 3 |
| 4 | 5 |
1 Шаг:
| 1 | 2 | 3 | |
| 4 | 5 | ||
| ^ | Удалили элемент 5. | ||
| used |
2 Шаг:
| 1 | 2 | 3 | |
| 4 | |||
| ^ | Удалили элемент 4. Так как он является первым в подмножестве, то мы не можем заменить его на другой. | ||
| 5 | used |
3 Шаг:
| 1 | 2 | 3 | 4 | |
| ^ | Дополнили первое подмножество элементом 4 | |||
| 5 | used |
4 Шаг:
| 1 | 2 | 3 | 4 | |
| 5 | Дописали лексикографически минимальный хвост | |||
| used |
