Получение следующего объекта
Версия от 09:18, 26 декабря 2013; 194.85.161.36 (обсуждение) (→Специализация алгоритма для генерации следующего сочетания)
Алгоритм
| Определение: |
| Получение следующего объекта — это нахождение объекта, следующего за данным в лексикографическом порядке. |
Объект называется следующим за , если и не найдется такого , что .
Отсюда понятен алгоритм:
- Находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта
- К оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило )
- Дописываем минимальный возможный хвост
По построению получаем, что — минимально возможный.
Специализация алгоритма для генерации следующего битового вектора
- Находим минимальный суффикс, в котором есть 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]
for j = i + 1 to n
if (a[j] < a[min]) and (a[j] > a[i])
min==j
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): array[1..N] of integer;
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]);
return(b[1..N]);
end
else
begin
return(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..k] of integer): array[1..k] of integer; // n,k - параметры сочетания.
var
i,j : integer;
b:array[1..k+1] of integer;
begin
for i := 1 to k do
b[i]:=a[i];
b[k + 1] := n + 1;
i := n;
while (i > 0) and ((b[i + 1] - b[i]) < 2) do
i := i - 1;
if i > 0 then
begin
b[i] := b[i] + 1;
for j := i + 1 to k do
b[j] := b[j - 1] + 1;
for i := 1 to k do
a[i] := b[i];
return(a[1..k]);
end
else
return(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:list): list;
var i : integer;
begin
b.set(b.size,b.get(b.size) - 1);
b.set(b.size-1,b.get(b.size-1) + 1);
if b.get(b.size-1) > b.get(b.size) then
begin
b.set(b.size-1,b.get(b.size-1) + b.get(b.size));
b.size(b.size-1);
end
else
begin
while b.get(b.size-1) * 2 <= b.get(b.size) do
begin
b.add(b.get(b.size)-b.get(b.size-1));
b.set(b.size-1,b.get(b.size-1));
end;
end;
return(b);
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 натуральных чисел:
Упорядочим все разбиения на множества лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество лексикографически меньше подмножества , если верно одно из следующих условий:
- существует такое, что , , для всех если и только если , и существует такое что ;
- и для всех и \ .
Разбиения упорядочены лексикографически следующим образом. Разбиение лексикографически меньше разбиения если существует такое , что .
Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:
- Будем хранить подмножества списке списков, например, разбиение будет выглядеть так:
| 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]) // удаляем j элемент i подмножества и добавляем его в список
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 |
