Получение следующего объекта — различия между версиями
(→Специализация алгоритма для генерации следующего разбиения на подмножества) |
Admin (обсуждение | вклад) (→Специализация алгоритма для генерации следующего разбиения на подмножества) |
||
(не показано 100 промежуточных версий 16 участников) | |||
Строка 6: | Строка 6: | ||
Отсюда понятен алгоритм: | Отсюда понятен алгоритм: | ||
− | * | + | * находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта <tex>P</tex>, |
− | * | + | * к оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>), |
− | * | + | * дописываем минимальный возможный хвост. |
По построению получаем, что <tex>Q</tex> {{---}} минимально возможный. | По построению получаем, что <tex>Q</tex> {{---}} минимально возможный. | ||
− | == Специализация алгоритма для генерации следующего | + | == Специализация алгоритма для генерации следующего битового вектора == |
* Находим минимальный суффикс, в котором есть <tex>0</tex>, его можно увеличить, не меняя оставшейся части | * Находим минимальный суффикс, в котором есть <tex>0</tex>, его можно увеличить, не меняя оставшейся части | ||
* Вместо <tex>0</tex> записываем <tex>1</tex> | * Вместо <tex>0</tex> записываем <tex>1</tex> | ||
* Дописываем минимально возможный хвост из нулей | * Дописываем минимально возможный хвост из нулей | ||
− | + | '''int[]''' nextVector('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина вектора</font> | |
− | + | '''while''' (n >= 0) '''and''' (a[n] != 0) | |
− | '''if''' | + | a[n] = 0 |
− | + | n-- | |
− | + | '''if''' n == -1 | |
− | + | '''return''' ''null'' | |
− | + | a[n] = 1 | |
− | + | '''return''' a | |
− | + | Приведённый алгоритм эквивалентен прибавлению единицы к битовому вектору. | |
=== Пример работы === | === Пример работы === | ||
{| class="wikitable" border = 1 | {| class="wikitable" border = 1 | ||
− | |0||1||style="background:#FFCC00" | + | |0||1||0||1||style="background:#FFCC00"|1||исходный битовый вектор |
|- | |- | ||
− | | || || | + | | || || || ||^|| начинаем идти с конца |
|- | |- | ||
− | |0||1||style="background:#FFCC00"| | + | |0||1||0||style="background:#FFCC00"|0||style="background:#FFCC00"|0|| пока элементы равны 1, заменяем их на 0 |
|- | |- | ||
− | |0 | + | |0||1||style="background:#FFCC00"|1||0||0|| меняем первый не удовлетворяющий условию цикла элемент на 1 |
|- | |- | ||
|'''0'''||'''1'''||'''1'''||'''0'''||'''0'''||следующий битовый вектор | |'''0'''||'''1'''||'''1'''||'''0'''||'''0'''||следующий битовый вектор | ||
|} | |} | ||
− | == Специализация алгоритма для генерации | + | == Специализация алгоритма для генерации следующей перестановки == |
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример) | * Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример) | ||
* Меняем его с минимальным элементом, большим нашего, стоящим правее | * Меняем его с минимальным элементом, большим нашего, стоящим правее | ||
* Перевернем правую часть | * Перевернем правую часть | ||
− | + | '''int[]''' nextPermutation('''int[]''' a): <font color=green>// <tex>n</tex> {{---}} длина перестановки</font> | |
− | '''for''' i = n - | + | '''for''' i = n - 2 '''downto''' 0 |
− | + | '''if''' a[i] < a[i + 1] | |
− | + | min = i + 1; | |
− | + | '''for''' j = i + 1 '''to''' n - 1 | |
− | + | '''if''' (a[j] < a[min]) '''and''' (a[j] > a[i]) | |
− | + | min = j | |
− | + | swap(a[i], a[min]) | |
− | + | reverse(a, i + 1, n - 1) | |
− | return | + | '''return''' a |
+ | '''return''' ''null'' | ||
=== Пример работы === | === Пример работы === | ||
Строка 68: | Строка 69: | ||
|} | |} | ||
− | == Специализация алгоритма для генерации следующей | + | == Специализация алгоритма для генерации следующей мультиперестановки == |
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример). | * Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример). | ||
* Меняем его с минимальным элементом, большим нашего, стоящим правее. | * Меняем его с минимальным элементом, большим нашего, стоящим правее. | ||
* Переворачиваем правую часть. | * Переворачиваем правую часть. | ||
− | ''' | + | '''int[]''' nextMultiperm('''int[]''' b): <font color=green>// <tex>n</tex> {{---}} длина мультиперестановки</font> |
− | + | i = n - 2 | |
− | + | '''while''' (i >= 0) '''and''' (b[i] >= b[i + 1]) | |
− | + | i-- | |
− | + | '''if''' i >= 0 | |
− | |||
− | |||
− | |||
j = i + 1 | j = i + 1 | ||
− | '''while''' (j < | + | '''while''' (j < n - 1) '''and''' (b[j + 1] > b[i]) |
j++ | j++ | ||
swap(b[i] , b[j]) | swap(b[i] , b[j]) | ||
− | + | reverse(b, i + 1, n - 1) | |
− | + | '''return''' b | |
− | + | '''else''' | |
− | + | '''return''' ''null'' | |
− | |||
− | |||
− | |||
− | |||
− | |||
=== Пример работы === | === Пример работы === | ||
Строка 107: | Строка 100: | ||
|} | |} | ||
− | == Специализация алгоритма для генерации | + | == Специализация алгоритма для генерации следующего сочетания == |
* Добавим в конец массива с сочетанием <tex>N+1</tex> – максимальный элемент. | * Добавим в конец массива с сочетанием <tex>N+1</tex> – максимальный элемент. | ||
− | * Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на <tex>2</tex>. | + | * Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на <tex>2</tex> и больше. |
* Увеличим найденный элемент на <tex>1</tex>, и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание. | * Увеличим найденный элемент на <tex>1</tex>, и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание. | ||
− | ''' | + | '''int[]''' nextChoose('''int[]''' a, '''int''' n, '''int''' k): <font color=green>// <tex>n,k </tex> {{---}} параметры сочетания</font> |
− | + | '''for''' i = 0 '''to''' k - 1 | |
− | + | b[i] = a[i] | |
− | + | b[k] = n + 1 | |
− | + | i = k - 1 | |
− | '''for''' i = | + | '''while''' (i >= 0) '''and''' (b[i + 1] - b[i] < 2) |
− | |||
− | b[k | ||
− | i = | ||
− | '''while''' (i > 0) '''and''' | ||
i-- | i-- | ||
− | '''if''' i > 0 | + | '''if''' i >= 0 |
− | |||
b[i]++ | b[i]++ | ||
− | '''for''' j = i + 1 '''to''' k | + | '''for''' j = i + 1 '''to''' k - 1 |
− | + | b[j] = b[j - 1] + 1 | |
− | '''for''' i = | + | '''for''' i = 0 '''to''' k - 1 |
− | + | a[i] = b[i] | |
− | + | '''return''' a | |
− | |||
'''else''' | '''else''' | ||
− | + | '''return''' ''null'' | |
− | |||
=== Пример работы === | === Пример работы === | ||
Строка 151: | Строка 137: | ||
|} | |} | ||
− | == Специализация алгоритма для генерации следующего | + | == Специализация алгоритма для генерации следующего разбиения на слагаемые == |
Рассматриваемый алгоритм находит следующее [[комбинаторные объекты|разбиение на слагаемые]], при этом разбиение упорядоченно по возрастанию. | Рассматриваемый алгоритм находит следующее [[комбинаторные объекты|разбиение на слагаемые]], при этом разбиение упорядоченно по возрастанию. | ||
* Увеличим предпоследнее слагаемое на <tex>1</tex>, уменьшим последнее слагаемое на <tex>1</tex>. | * Увеличим предпоследнее слагаемое на <tex>1</tex>, уменьшим последнее слагаемое на <tex>1</tex>. | ||
** Если предпоследнее слагаемое стало больше последнего, то увеличиваем предпоследнее слагаемое на величину последнего. | ** Если предпоследнее слагаемое стало больше последнего, то увеличиваем предпоследнее слагаемое на величину последнего. | ||
− | ** Если предпоследнее слагаемое меньше последнего, то разбиваем последнее слагаемое <tex>s</tex> на два слагаемых <tex>a</tex> и <tex>b</tex> таких, что <tex>a</tex> равно предпоследнему слагаемому, а <tex>b = s - a</tex>. Повторяем этот процесс, пока разбиение остается корректным, то есть предпоследнее слагаемое хотя бы в два раза меньше последнего. | + | ** Если предпоследнее слагаемое умноженное на 2 меньше последнего, то разбиваем последнее слагаемое <tex>s</tex> на два слагаемых <tex>a</tex> и <tex>b</tex> таких, что <tex>a</tex> равно предпоследнему слагаемому, а <tex>b = s - a</tex>. Повторяем этот процесс, пока разбиение остается корректным, то есть предпоследнее слагаемое хотя бы в два раза меньше последнего. |
<code> | <code> | ||
− | <font color=green>// <tex>b</tex> {{---}} список, содержащий разбиение данного числа | + | <font color=green>// <tex>b</tex> {{---}} список, содержащий разбиение данного числа <tex>b.size</tex>{{---}} его размер </font> |
− | ''' | + | '''list<int>''' nextPartition('''list<int>''' b): |
− | + | b[b.size - 1]-- | |
− | + | b[b.size - 2]++ | |
− | b[b.size]-- | + | '''if''' b[b.size - 2] > b[b.size - 1] |
− | b[b.size - | + | b[b.size - 2] += b[b.size - 1] |
− | '''if''' b[b.size - | + | b.remove(b.size - 1) |
− | |||
− | b[b.size - | ||
− | b. | ||
− | |||
'''else''' | '''else''' | ||
− | + | '''while''' b[b.size - 2] * 2 <= b[b.size - 1] | |
− | '''while''' b[b.size - | + | b.add(b[b.size - 1] - b[b.size - 2]) |
− | + | b[b.size - 2] = b[b.size - 3] | |
− | b.add(b[b.size] - b[b.size - | ||
− | b[b.size - | ||
− | |||
− | |||
'''return''' b | '''return''' b | ||
− | |||
</code> | </code> | ||
Строка 185: | Строка 162: | ||
|1||style="background:#FFCC00"|1||style="background:#FFCC00"|7|| || ||Прибавим 1 + 1, вычтем 7 - 1. | |1||style="background:#FFCC00"|1||style="background:#FFCC00"|7|| || ||Прибавим 1 + 1, вычтем 7 - 1. | ||
|- | |- | ||
− | |1||style="background:#FFCC00"|2||style="background:#FFCC00"|6|| || ||Проверяем: 2<6, значит разбиваем 6 пока оно не станет | + | |1||style="background:#FFCC00"|2||style="background:#FFCC00"|6|| || ||Проверяем: 2 < 6, значит разбиваем 6 пока оно не станет меньше 4 |
|- | |- | ||
|1||2||style="background:#FFCC00"|2||style="background:#FFCC00"|4|| || | |1||2||style="background:#FFCC00"|2||style="background:#FFCC00"|4|| || | ||
Строка 197: | Строка 174: | ||
|1||style="background:#FFCC00"|4||style="background:#FFCC00"|5||Прибавим 4 + 1, вычтем 5 - 1. | |1||style="background:#FFCC00"|4||style="background:#FFCC00"|5||Прибавим 4 + 1, вычтем 5 - 1. | ||
|- | |- | ||
− | |1||style="background:#FFCC00"|5||style="background:#FFCC00"|4||Проверяем: 5>4, значит прибавим к 5 + 4. | + | |1||style="background:#FFCC00"|5||style="background:#FFCC00"|4||Проверяем: 5 > 4, значит прибавим к 5 + 4. |
|- | |- | ||
|1||9||style="background:#FFCC00"|4||Удалим последний элемент. | |1||9||style="background:#FFCC00"|4||Удалим последний элемент. | ||
|- | |- | ||
|'''1'''||'''9'''||||Следующее разбиение на слагаемые числа 10. | |'''1'''||'''9'''||||Следующее разбиение на слагаемые числа 10. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|} | |} | ||
== См.также == | == См.также == | ||
+ | * [[Получение предыдущего объекта]] | ||
* [[Получение объекта по номеру]] | * [[Получение объекта по номеру]] | ||
* [[Получение номера по объекту]] | * [[Получение номера по объекту]] |
Текущая версия на 23:35, 8 января 2024
Алгоритм
Определение: |
Получение следующего объекта — это нахождение объекта, следующего за данным в лексикографическом порядке. |
Объект
называется следующим за , если и не найдется такого , что .Отсюда понятен алгоритм:
- находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта ,
- к оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило ),
- дописываем минимальный возможный хвост.
По построению получаем, что
— минимально возможный.Специализация алгоритма для генерации следующего битового вектора
- Находим минимальный суффикс, в котором есть , его можно увеличить, не меняя оставшейся части
- Вместо записываем
- Дописываем минимально возможный хвост из нулей
int[] nextVector(int[] a): //
— длина вектора
while (n >= 0) and (a[n] != 0)
a[n] = 0
n--
if n == -1
return null
a[n] = 1
return a
Приведённый алгоритм эквивалентен прибавлению единицы к битовому вектору.
Пример работы
0 | 1 | 0 | 1 | 1 | исходный битовый вектор |
^ | начинаем идти с конца | ||||
0 | 1 | 0 | 0 | 0 | пока элементы равны 1, заменяем их на 0 |
0 | 1 | 1 | 0 | 0 | меняем первый не удовлетворяющий условию цикла элемент на 1 |
0 | 1 | 1 | 0 | 0 | следующий битовый вектор |
Специализация алгоритма для генерации следующей перестановки
- Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
- Меняем его с минимальным элементом, большим нашего, стоящим правее
- Перевернем правую часть
int[] nextPermutation(int[] a): //
— длина перестановки
for i = n - 2 downto 0
if a[i] < a[i + 1]
min = i + 1;
for j = i + 1 to n - 1
if (a[j] < a[min]) and (a[j] > a[i])
min = j
swap(a[i], a[min])
reverse(a, i + 1, n - 1)
return a
return null
Пример работы
1 | 3 | 2 | 5 | 4 | исходная перестановка |
^ | находим элемент, нарушающий убывающую последовательность | ||||
^ | минимальный элемент больше нашего | ||||
1 | 3 | 4 | 5 | 2 | меняем их местами |
1 | 3 | 4 | 2 | 5 | разворачивам правую часть |
1 | 3 | 4 | 2 | 5 | следующая перестановка |
Специализация алгоритма для генерации следующей мультиперестановки
- Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример).
- Меняем его с минимальным элементом, большим нашего, стоящим правее.
- Переворачиваем правую часть.
int[] nextMultiperm(int[] b): //
— длина мультиперестановки
i = n - 2
while (i >= 0) and (b[i] >= b[i + 1])
i--
if i >= 0
j = i + 1
while (j < n - 1) and (b[j + 1] > b[i])
j++
swap(b[i] , b[j])
reverse(b, i + 1, n - 1)
return b
else
return null
Пример работы
1 | 2 | 3 | 1 | 2 | 3 | Исходная перестановка. |
^ | Находим элемент, нарушающий убывающую последовательность. | |||||
^ | Минимальный элемент больше нашего. | |||||
1 | 2 | 3 | 1 | 3 | 2 | Меняем их местами. |
1 | 2 | 3 | 1 | 3 | 2 | Следующая мультиперестановка. |
Специализация алгоритма для генерации следующего сочетания
- Добавим в конец массива с сочетанием – максимальный элемент.
- Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на и больше.
- Увеличим найденный элемент на , и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание.
int[] nextChoose(int[] a, int n, int k): //
— параметры сочетания
for i = 0 to k - 1
b[i] = a[i]
b[k] = n + 1
i = k - 1
while (i >= 0) and (b[i + 1] - b[i] < 2)
i--
if i >= 0
b[i]++
for j = i + 1 to k - 1
b[j] = b[j - 1] + 1
for i = 0 to k - 1
a[i] = b[i]
return a
else
return null
Пример работы
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 | Следующее сочетание. |
Специализация алгоритма для генерации следующего разбиения на слагаемые
Рассматриваемый алгоритм находит следующее разбиение на слагаемые, при этом разбиение упорядоченно по возрастанию.
- Увеличим предпоследнее слагаемое на
- Если предпоследнее слагаемое стало больше последнего, то увеличиваем предпоследнее слагаемое на величину последнего.
- Если предпоследнее слагаемое умноженное на 2 меньше последнего, то разбиваем последнее слагаемое на два слагаемых и таких, что равно предпоследнему слагаемому, а . Повторяем этот процесс, пока разбиение остается корректным, то есть предпоследнее слагаемое хотя бы в два раза меньше последнего.
, уменьшим последнее слагаемое на .
//— список, содержащий разбиение данного числа — его размер list<int> nextPartition(list<int> b): b[b.size - 1]-- b[b.size - 2]++ if b[b.size - 2] > b[b.size - 1] b[b.size - 2] += b[b.size - 1] b.remove(b.size - 1) else while b[b.size - 2] * 2 <= b[b.size - 1] b.add(b[b.size - 1] - b[b.size - 2]) b[b.size - 2] = b[b.size - 3] return b
Пример работы
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. |