Разбиения положительного целого числа п является невозрастающим массивом положительных целых чиселразбиения целых чисел
а [1], а [2], ..., а [м]
удовлетворяющих
a [1] + a [2] + ... + a [m] = n.
m называется длиной этого раздела.
Мы можем перечислить все разделы n в указанном порядке. Например, если мы используем правило , по которому лексикография сортирует все английские слова, это называется лексикографическим порядком. Другой способ, если мы используем правило, с помощью которого язык C сравнивает строки, называется обратным порядком лексикографии. И есть также порядок colex.
Для создания всех разделов одного целого числа п, у нас есть хороший алгоритм, предложенный Стойменович, которая уже была включена в книге Кнута.
Чтобы сгенерировать все разделы n с длиной точно m, мы можем использовать порядок colex, этот алгоритм также включен в книгу Кнута.
Чтобы сгенерировать все разбиения n со всеми их элементами, не превышающими k, мы можем использовать алгоритм в 1, просто изменив его начальное условие и условие выхода цикла.
Вот мой вопрос: как сгенерировать те разделы, длина которых точно равна m, а их элементы не превышают k?
Здесь m и k - постоянные. Разумеется, разбиение с его элементами, не превышающими k, эквивалентно его первому элементу, не превосходящему k.
О, я думаю, что решил. для
а [1] + а [2] + ... + а [м] = п
может быть записана в виде
(K + 1-а [1]) + (к + 1-a [2]) + ... + (k + 1-a [m]) = m (k + 1) -n
, а последний представляет собой просто обратное разбиение m (k + 1) -n!
Если вы решили его, разместите его как ответ и примите его. (Я не уверен, как трюк запрещает отрицательные числа, хотя я об этом не думал.) – sdcvvc
Как разбиение m (k + 1) -1 на фиксированную длину m? – Beta