Ваша задача проста: Дано целое число N , Ouput каждый список положительных целых чисел, сумм к N . Например, если ввод был 5, вы должны вывести
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]
Эти списки не должны выводиться в каком-либо определенном порядке, равно как и числа внутри каждого списка. Например, это также будет приемлемым выводом для '5':
[1, 1, 1, 2]
[5]
[3, 1, 1]
[2, 1, 2]
[4, 1]
[1, 1, 1, 1, 1]
[2, 3]
Вы можете смело предположить, что ввод будет положительным целым числом, и вы можете взять это число в любом разумном формате.
Вы не можете использовать любые встроенные функции, которые делают это.
Если ваша программа либо дает сбой, либо занимает слишком много времени для большого N, это нормально, но вы должны как минимум вывести правильный вывод для первых 15.
Применяются стандартные лазейки, и выигрывает самый короткий ответ в байтах!
Тест IO
1:
[[1]]
2:
[[1, 1], [2]]
3:
[[1, 1, 1], [1, 2], [3]]
4:
[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]
5:
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 4], [2, 3], [5]]
7:
[[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 3], [1, 1, 1, 2, 2], [1, 1, 1, 4], [1, 1, 2, 3], [1, 1, 5], [1, 2, 2, 2], [1, 2, 4], [1, 3, 3], [1, 6], [2, 2, 3], [2, 5], [3, 4], [7]]
10:
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 6], [1, 1, 1, 2, 2, 3], [1, 1, 1, 2, 5], [1, 1, 1, 3, 4], [1, 1, 1, 7], [1, 1, 2, 2, 2, 2], [1, 1, 2, 2, 4], [1, 1, 2, 3, 3], [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 1, 8], [1, 2, 2, 2, 3], [1, 2, 2, 5], [1, 2, 3, 4], [1, 2, 7], [1, 3, 3, 3], [1, 3, 6], [1, 4, 5], [1, 9], [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5], [2, 4, 4], [2, 8], [3, 3, 4], [3, 7], [4, 6], [5, 5], [10]]
Супер большой тестовый пример: 15 должен вывести это
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 11], [1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 2, 2, 8], [1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 2, 3, 7], [1, 1, 1, 2, 4, 6], [1, 1, 1, 2, 5, 5], [1, 1, 1, 2, 10], [1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 3, 3, 6], [1, 1, 1, 3, 4, 5], [1, 1, 1, 3, 9], [1, 1, 1, 4, 4, 4], [1, 1, 1, 4, 8], [1, 1, 1, 5, 7], [1, 1, 1, 6, 6], [1, 1, 1, 12], [1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 2, 5], [1, 1, 2, 2, 2, 3, 4], [1, 1, 2, 2, 2, 7], [1, 1, 2, 2, 3, 3, 3], [1, 1, 2, 2, 3, 6], [1, 1, 2, 2, 4, 5], [1, 1, 2, 2, 9], [1, 1, 2, 3, 3, 5], [1, 1, 2, 3, 4, 4], [1, 1, 2, 3, 8], [1, 1, 2, 4, 7], [1, 1, 2, 5, 6], [1, 1, 2, 11], [1, 1, 3, 3, 3, 4], [1, 1, 3, 3, 7], [1, 1, 3, 4, 6], [1, 1, 3, 5, 5], [1, 1, 3, 10], [1, 1, 4, 4, 5], [1, 1, 4, 9], [1, 1, 5, 8], [1, 1, 6, 7], [1, 1, 13], [1, 2, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 2, 4], [1, 2, 2, 2, 2, 3, 3], [1, 2, 2, 2, 2, 6], [1, 2, 2, 2, 3, 5], [1, 2, 2, 2, 4, 4], [1, 2, 2, 2, 8], [1, 2, 2, 3, 3, 4], [1, 2, 2, 3, 7], [1, 2, 2, 4, 6], [1, 2, 2, 5, 5], [1, 2, 2, 10], [1, 2, 3, 3, 3, 3], [1, 2, 3, 3, 6], [1, 2, 3, 4, 5], [1, 2, 3, 9], [1, 2, 4, 4, 4], [1, 2, 4, 8], [1, 2, 5, 7], [1, 2, 6, 6], [1, 2, 12], [1, 3, 3, 3, 5], [1, 3, 3, 4, 4], [1, 3, 3, 8], [1, 3, 4, 7], [1, 3, 5, 6], [1, 3, 11], [1, 4, 4, 6], [1, 4, 5, 5], [1, 4, 10], [1, 5, 9], [1, 6, 8], [1, 7, 7], [1, 14], [2, 2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 3, 4], [2, 2, 2, 2, 7], [2, 2, 2, 3, 3, 3], [2, 2, 2, 3, 6], [2, 2, 2, 4, 5], [2, 2, 2, 9], [2, 2, 3, 3, 5], [2, 2, 3, 4, 4], [2, 2, 3, 8], [2, 2, 4, 7], [2, 2, 5, 6], [2, 2, 11], [2, 3, 3, 3, 4], [2, 3, 3, 7], [2, 3, 4, 6], [2, 3, 5, 5], [2, 3, 10], [2, 4, 4, 5], [2, 4, 9], [2, 5, 8], [2, 6, 7], [2, 13], [3, 3, 3, 3, 3], [3, 3, 3, 6], [3, 3, 4, 5], [3, 3, 9], [3, 4, 4, 4], [3, 4, 8], [3, 5, 7], [3, 6, 6], [3, 12], [4, 4, 7], [4, 5, 6], [4, 11], [5, 5, 5], [5, 10], [6, 9], [7, 8], [15]]
Каталог
Фрагмент стека в нижней части этого поста создает каталог из ответов а) в виде списка кратчайшего решения для каждого языка и б) в качестве общей таблицы лидеров.
Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:
## Language Name, N bytes
где N
размер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Ответы:
Pyth,
109 байтовНе слишком уверен, что это не обман, но в правилах сказано, что нельзя использовать целочисленное разбиение (это не указано четко в самом вопросе, но комментарий ОП в вопросе говорит о целочисленном разбиении). Я использую раздел списка
строк, который создает фрагменты списка, которые соединяются до «материнского» списка. Я считаю, что должен поблагодарить @Maltysen за идею использования списков, а не строк.n = 15 занимает меньше одной секунды на моей машине.
В псевдокоде потока данных:
Попробуйте это онлайн здесь.
источник
{mSlMd./*N
сохраняет байтPyth, 18 байт
Попробуйте онлайн! (В
y
конце используется для вызова функции)Это довольно быстро.
Это использует рекурсию. Если ввод
b
, мой метод будет генерировать разделы из0
вb-1
, а затем генерировать правильные разделы из каждого.Например, когда
b=4
:b=0
дает[[]]
b=1
дает[[1]]
b=2
дает[[2], [1, 1]]
b=3
дает[[3], [1, 2], [1, 1, 1]]
Затем, к каждому разделу в
b=0
, добавьте4
(чтобы получить сумму 4); к каждому разделу вb=1
, добавить3
(чтобы сделать сумму4
); и т.п.Это в основном, как это работает.
источник
MATL , 20 байтов
Попробуйте онлайн!
Для ввода
15
требуется около 2 секунд в онлайн-компиляторе.объяснение
Это работает путем генерации точек разбиения и последующего преобразования в длины разделов . Под этим я подразумеваю следующее. При заданном входе N = 5 возможное разбиение будет [2 2 1]. Это представлено точками разбиения [0 2 4 5], так что последовательные различия (или длины) точек разбиения дают результирующее разбиение входного номера.
Все массивы точек разбиения начинаются с 0 и заканчиваются N . Число k промежуточных точек варьируется от 0 до N -1. Для заданных N и k промежуточные точки могут быть сгенерированы как комбинация чисел [1, 2, ..., N -1], взятых k за раз.
Несколько массивов точек разбиения могут привести к одному и тому же результату в другом порядке. Например, точки разбиения [0 1 3 5] дадут длины разбиения [1 2 2], т. Е. Такие же, как предыдущие [2 2 1], только в другом порядке. Это необходимо учитывать, сортируя каждый массив длин разделов и удаляя дубликаты .
источник
Haskell, 53 байта
источник
J,
4942363532 байтаСейчас молчаливо!
Создает целочисленное разбиение n , создавая целочисленные разбиения от 1 до n . Вычисляет результат для n = 15 в миллисекундах.
Начиная с начального целочисленного раздела,
[[1]]
который соответствует n = 1, создайте следующий целочисленный раздел, соединив результаты двух операций: добавление 1 к каждому разделу; увеличивая наименьшее значение на 1 в каждом разделе. Конечно, дубликаты разделов будут удалены. Чтобы получить целочисленный раздел n = 2 и далее,использование
объяснение
Поскольку J не поддерживает рваные массивы, каждый раздел должен быть упакован, чтобы они не были дополнены нулями при добавлении к другим разделам.
источник
Python, 65 байт
Python 3
Эта функция накапливает раздел и печатает выходные данные, разветвляясь на выбор. Он решает, сколько 1 нужно поместить в раздел, сколько 2 и так далее. Для каждого значения
i
оно либоi
и уменьшаетn
доn-i
илиi+1
Если
i>n
, тогда больше не могут быть сделаны детали, поэтому он останавливается. Еслиn
падает до0
, раздел будет успешным и будет напечатан.Python 2
Рекурсивный метод, который выводит список разделов. Как и в коде Python 3, он подсчитывает размер части
i
и на каждом шаге решает, добавлять ли другую часть размераi
или останавливать.Оба из них делают
n=15
почти мгновенно.источник
Javascript, 194 байта
Номера уменьшенная
Поиск уникальных объектов путем сортировки и сравнения со строкой является довольно хакерским, но, вероятно, экономит место.
источник
Quite a hack but saves space
Это именно то, о чем этот сайт. : DPython 3.5,
8272 байтаВозвращает набор кортежей. n = 15 заканчивается мгновенно.
Проверьте это на repl.it .
источник
Haskell, 44 байта
Вспомогательная функция
n%m
дает разбиениеn
на части≥m
, используя основную функциюm=1
. Это ветви каждой первой записиj
сm≤j≤n
, рекурсиями на оставшуюся часть разделаn-j
на часть , которые являются , по крайней мереj
. Базовый случайn==0
дает только пустой раздел.источник
Pyth, 17 байт
Определяет функцию с именем
y
. Попробуйте онлайн .источник
Желе , 9 байт
Попробуйте онлайн!
Как это работает
источник
J, 39 байт
Это монадический глагол, который принимает целое число и возвращает массив штучных массивов. Попробуй это здесь. Использование:
На входе 15 он работает около секунды на моей машине.
объяснение
Эта задача сразу же выглядела как работа для Catalog (
{
) и Cut (;.
). Схема алгоритма:n
.n
массив фиктивных длин вдоль 1 с и перечислите длины каждой части.Видимо, у Луиса Мендо тоже была такая же идея .
Объяснение кода:
источник
;.
снова.Brachylog , 33 байта (не конкурирует)
Это не конкурирует из-за исправления ошибки.
Это займет около 1 секунды
15
на моей машине. Для20
и больше это вылетает заOut of global stack
исключением.объяснение
При этом не используется никакого встроенного разделения, и вместо этого используется тот факт, что
+
оба способа работают через распространение ограничений.Основной предикат:
Предикат 1:
источник
Mathematica,
6254 байтаРазделы целого числа n можно найти, решая для n- наборов неотрицательных целых чисел ( c 1 , c 2 , ..., c n ) таких, что c 1 + 2 c 2 + ... + n c n = п .
FrobeniusSolve
способен найти все решения этого уравнения, которые используются для создания такого количества копий их соответствующих значений, чтобы найти все целочисленные разбиения n .источник
FrobeniusSolve
не находит целочисленных разбиений, он находит все решения неотрицательных целых чиселx1 ... xN
для уравненийa1 x1 + a2 x2 + ... aN xN = b
заданной формыa1 ... aN
иb
.JavaScript
(Firefox 30-57) 79ES6, 65 байтПорт решения @ xnor's Python. (Если бы только я заметил, что вы могли бы вернуться,
m
а такжеn
...)источник