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

Составление следующего разбиения

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

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

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

n — натуральное число;

pj — j-ое натуральное слагаемое;

mj — счётчик j-ого натурального слагаемого;

k — число натуральных слагаемых разбиения, равное сумме счётчиков;

{R1,R2,…,Rk} — разбиение числа n на k натуральных слагаемых.

Алгоритм разбиений[править]

Входные данные: n; k; {R1,R2,…,Rk}.

КОМ45.JPG

Выходные данные: k; {R1,R2,…,Rk}.

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

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


Ссылки[править]