Составление следующего сочетания с повторениями

Составление следующего сочетания с повторениями — это алгоритм (комбинаторная операция) получения для сочетания с повторениями следующего в лексикографическом порядке сочетания с повторениями.

Обозначения

Введём обозначения:

n — число элементов конечного множества;

k — число элементов в сочетании с повторениями;

{C₁,C₂,…,C_k} — сочетание с повторениями k номеров элементов множества из n элементов.

Алгоритм сочетаний с повторениями

Входные данные: n; k; {C₁,C₂,…,C_k}.

1. Сортировка {C₁,C₂,…,C_k} по возрастанию.
2. i = k, C₀ = 0.
3. Если C_i = n, то i = i − 1 и идти к 3.
4. C_i = C_i + 1; j = i + 1.
5. C_j = C_j−1; j = j + 1.
6. Если j ≤ k, то идти к 5.
7. {C₁,C₂,…,C_k} — сочетание с повторениями.

Выходные данные: {C₁,C₂,…,C_k}.

• Заметим, что алгоритм для лексикографически последнего сочетания с повторениями даёт, как следующее, первое сочетание с повторениями.

Другие алгоритмы:

• составление перестановок;
• составление лексикографических перестановок;
• составление следующей перестановки;
• составление сочетаний;
• составление лексикографических сочетаний;
• составление следующего сочетания;
• составление размещений;
• составление лексикографических размещений;
• составление следующего размещения;
• составление разбиений;
• составление лексикографических разбиений;
• составление следующего разбиения;
• составление распределений;
• составление лексикографических распределений;
• составление следующего распределения;
• составление лексикографических перестановок с повторениями;
• составление следующей перестановки с повторениями;
• составление лексикографических сочетаний с повторениями;
• составление следующего сочетания с повторениями;
• составление лексикографических размещений с повторениями;
• составление следующего размещения с повторениями.

Ссылки

• Участник:Logic-samara