Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

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

Материал из Циклопедии
Перейти к навигации Перейти к поиску

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

Обозначения[править]

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

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

{C1,C2,…,Ck} — сочетание с повторениями k номеров элементов множества из n элементов.

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

Входные данные: n; k; {C1,C2,…,Ck}.

  1. Сортировка {C1,C2,…,Ck} по возрастанию.
  2. i = k, C0 = 0.
  3. Если Ci = n, то i = i − 1 и идти к 3.
  4. Ci = Ci + 1; j = i + 1.
  5. Cj = Cj−1; j = j + 1.
  6. Если j ≤ k, то идти к 5.
  7. {C1,C2,…,Ck} — сочетание с повторениями.

Выходные данные: {C1,C2,…,Ck}.

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

Другие алгоритмы:[править]