Получение следующего объекта
Версия от 16:45, 21 ноября 2014; 109.205.252.46 (обсуждение) (→Специализация алгоритма для генерации следующего битового вектора)
Алгоритм
| Определение: |
| Получение следующего объекта — это нахождение объекта, следующего за данным в лексикографическом порядке. |
Объект называется следующим за , если и не найдется такого , что .
Отсюда понятен алгоритм:
- Находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта
- К оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило )
- Дописываем минимальный возможный хвост
По построению получаем, что — минимально возможный.
Специализация алгоритма для генерации следующего битового вектора
- Находим минимальный суффикс, в котором есть , его можно увеличить, не меняя оставшейся части
- Вместо записываем
- Дописываем минимально возможный хвост из нулей
function nextVector(a:array[1..n] of byte):array[1..n] of byte; // n - длина вектора
for i = n downto 1
if a[i] == 0
a[i] = 1
for j = i + 1 to n
a[j] = 0
break
return(a);
Пример работы
| 0 | 1 | 0 | 1 | 1 | исходный битовый вектор |
| ^ | находим элемент 0 (самый правый) | ||||
| 0 | 1 | 1 | 1 | 1 | меняем его на 1 |
| 0 | 1 | 1 | 0 | 0 | меняем элементы правее на нули |
| 0 | 1 | 1 | 0 | 0 | следующий битовый вектор |
Специализация алгоритма для генерации следующей перестановки
- Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
- Меняем его с минимальным элементом, большим нашего, стоящим правее
- Перевернем правую часть
function nextPermutation(a:array[1..n] of integer):array[1..n] of integer; // n - длина перестановки
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
return(a);
Пример работы
| 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 | Следующая мультиперестановка. |
Специализация алгоритма для генерации следующего сочетания
- Добавим в конец массива с сочетанием – максимальный элемент.
- Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на .
- Увеличим найденный элемент на , и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание.
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 | Следующее сочетание. |
Специализация алгоритма для генерации следующего разбиения на слагаемые
Рассматриваемый алгоритм находит следующее разбиение на слагаемые, при этом разбиение упорядоченно по возрастанию.
- Увеличим предпоследнее слагаемое на , уменьшим последнее слагаемое на .
- Если предпоследнее слагаемое стало больше последнего, то увеличиваем предпоследнее слагаемое на величину последнего.
- Если предпоследнее слагаемое меньше последнего, то разбиваем последнее слагаемое на два слагаемых и таких, что равно предпоследнему слагаемому, а . Повторяем этот процесс, пока разбиение остается корректным, то есть предпоследнее слагаемое хотя бы в два раза меньше последнего.
// b – список, содержащий разбиение данного числа, length – его размер.
function nextPartition(var b: list<int>): list<int>;
var i : integer;
begin
b[b.size] := b[b.size] - 1;
b[b.size - 1] := b[b.size - 1] + 1;
if b[b.size - 1] > b[b.size] then
begin
b[b.size - 1] := b[b.size - 1] + b[b.size];
b.pop();
end
else
begin
while b[b.size - 1] * 2 <= b[b.size] do
begin
b.add(b[b.size] - b[b.size - 1]);
b[b.size - 1] := b[b.size - 2];
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. |
| 1 | 4 | 5 | Прибавим 4 + 1, вычтем 5 - 1. |
| 1 | 5 | 4 | Проверяем: 5>4, значит прибавим к 5 + 4. |
| 1 | 9 | 4 | Удалим последний элемент. |
| 1 | 9 | Следующее разбиение на слагаемые числа 10. |
Специализация алгоритма для генерации следующего разбиения на подмножества
Рассмотрим множество первых n натуральных чисел:
Упорядочим все разбиения на множества лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество лексикографически меньше подмножества , если верно одно из следующих условий:
- существует такое, что , , для всех если и только если , и существует такое что ;
- и для всех и \ .
Разбиения упорядочены лексикографически следующим образом. Разбиение лексикографически меньше разбиения если существует такое , что .
Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:
- Будем хранить подмножества в списке списков, например, разбиение будет выглядеть так:
| 1 | 2 | 3 |
| 4 | 5 |
- Двигаясь снизу вверх и справа налево, будем удалять элементы, записывая их в отдельный массив. Будем повторять эту операцию, пока не сможем выполнить одно из действий, описанных ниже:
- Заменить рассматриваемый элемент уже удаленным. Из всех подходящих элементов выбираем минимальный. Важное замечание: мы не можем заменить первый элемент подмножества, мы можем только удалить его.
- Дополнить рассматриваемое подмножество уже удаленным элементом. Из всех подходящих элементов выбираем минимальный.
- Допишем лексикографически минимальный хвост подмножеств из оставшихся элементов.
function nextSetPartition(a:list<list<int>>):list<list<int>>;
// a - список, содержащий подмножества
// used - список, в котором мы храним удаленные элементы
used = list<int>();
fl = false
for i = a.size downto 1
if (used.size <> 0) and (used[used.size] > a[i][a[i].size]) then //если можем добавить в конец подмножества элемент из used
a[i].add(used[used.size]); //добавляем
used.remove(used.size);
break
for j = a[i].size downto 1
if (used.size <> 0) and (j <> 1) and (used[used.size] > a[i][j]) then //если можем заменить элемент, другим элементом из списка used
a[i][j] = used[used.size]; //заменяем
fl = true
break
if (fl) break
used.add(a[i][j]); // добавляем в used j элемент i-го подмножества
a[i].remove(j); // удаляем j элемент i-го подмножества
// далее выведем все получившиеся подмножества
sort(used)
for i = 1 to used.size
a.add(list<int>(used[i])); // добавляем лексикографически минимальных хвост
return(a);
Пример работы
Рассмотрим следующее разбиение:
| 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 |
