Учитывая положительное число n , выведите все различные мультипликативные разбиения n в любом удобном формате.
Мультипликативное разбиение n - это набор целых чисел, все больше единицы, так что их произведение равно n . Например, 20 имеет следующие различные мультипликативные разделы:
2 * 2 * 5
2 * 10
4 * 5
20
Порядок не имеет значения, так 2 * 2 * 5
же как и раздел 2 * 5 * 2
.
Примеры:
1 -> {}
2 -> {2}
4 -> {2, 2}, {4}
20 -> {2, 2, 5}, {2, 10}, {4, 5}, {20}
84 -> {2, 2, 3, 7}, {2, 2, 21}, {2, 14, 3}, {2, 6, 7}, {2, 42}, {4, 3, 7}, {28, 3}, {4, 21}, {6, 14}, {12, 7}, {84}
Ответы:
Брахилог , 16 байт
Это функция (не полная программа), которая принимает положительное число в качестве входных данных и генерирует все его мультипликативные разбиения. (Я также избегал использования каких-либо основных встроенных факторов факторизации в этом решении, в основном потому, что я не был уверен, что они помогут; в какой-то момент я мог бы попробовать и более сложное решение).
Попробуйте онлайн! (Вокруг этой функции был добавлен дополнительный код, чтобы превратить ее в полноценную программу; если вы предоставите функцию, показанную выше, для TIO напрямую, она запустит функцию, но нигде не распечатает свой вывод, что бесполезно в качестве демонстрации .)
Эта программа действительно разочаровывает меня, потому что большая часть ее работает вокруг ошибок в интерпретаторе брахилога и недостатков в его спецификации, а не на самом деле решения проблемы; но переводчик такой, какой он есть. (Даже с такой программой интерпретатор использует гораздо больше памяти, чем логически, и падает из-за истощения памяти, но, к счастью, при небольших проблемах ему удается сначала получить желаемый результат.) В гипотетической «идеальной версии Брахилога» Вы могли бы просто написать
~*.o.:{>1}a,
, что было бы на 4 байта короче, но мне нужно было добавить дополнительные ограничения, чтобы немного помочь интерпретатору. (Мне не очень нравится Brachylog, и я бы предпочел придерживаться Prolog, но для работы программы требовались похожие подсказки, а писать их было гораздо дольше. Так что Brachylog так и есть.)Объяснение:
Как обычно, программа на брахилоге представляет собой набор ограничений; по умолчанию первое ограничение ограничивает входные данные в отношении неизвестного (который я назову A ), второе ограничение ограничивает A в отношении второго неизвестного B и так далее, пока мы не достигнем результата. Некоторые символы, например
{}
, могут изменить этот общий поток, поэтому я использую другой набор букв (например, X / Y ) для представления неизвестных во вложенных предикатах.До сих пор неясно, как работает программа, поэтому давайте попробуем немного упростить ограничения. C , D , G , H и I одинаковы (и равны выходу). E и F также одинаковы (и равны входу). Таким образом, наши ограничения сводятся к следующему:
:{1<}a
требуется, чтобы его левый аргумент имел ограниченную длину, иначе интерпретатор входит в бесконечный цикл).Между прочим, я не указал явно, что все элементы вывода являются целыми числами, что может показаться необходимым; тем не менее, решатель ограничений Brachylog не может обрабатывать нецелые числа, поэтому он будет удобно создавать только те решения, которые включают целые числа.
Ясно, что «длина выходного сигнала меньше входного» будет истинной всякий раз, когда выходной сигнал является мультипликативным разделом входного сигнала (потому что 2 x > x для всех неотрицательных x , т.е. положительных 2 x ). Таким образом, мы можем игнорировать это ограничение; это только для того, чтобы дать интерпретатору брахилога рабочую стратегию для оценки программы. Другие ограничения (то, что выходные данные отсортированы, что его произведение является входным, и что все его элементы больше 1) являются определением мультипликативного разбиения, и, следовательно, эта функция в основном является прямой реализацией вопроса.
источник
Брахилог 1, 14 байтов
Попробуйте онлайн!
Brachylog 2,
1110 байт, языковые проблемы постдатПопробуйте онлайн!
Maltysen ответил на этот вопрос в 17 байтах Pyth, поэтому я предложил 16-байтовое решение Brachylog, которое работало путем перевода спецификации вопроса в Brachylog. Пока я этим занимался, Деннис написал 15-байтовое решение Jelly. Так что мне пришлось уменьшить до 14 байтов. Это функция, которая принимает входные данные в качестве аргумента и возвращает список всех разделов (а не генератор, как в моем другом решении).
Через некоторое время после того, как я написал этот ответ, нам с Деннисом удалось совместными усилиями получить решение Jelly до 11 байтов. Оказывается, вышла новая версия Brachylog с более кратким синтаксисом; это откладывает вызов, так что фактически не считается, но он может управлять 11-байтовым общим количеством слишком много, как только он выпущен; более поздние пересмотры языка (вдохновленные другими проблемами) могут составить всего 10, как показано здесь. Две программы идентичны, с единственным отличием в синтаксисе.
В отличие от моего другого решения, которое не использовало много «примитивов для игры в гольф», а скорее прямо указывало на проблему, оно игнорирует почти всю мощь ограничений брахилога и вместо этого производит наилучшее впечатление от Jelly, выписывая цепочку ограничений, для которых левый аргумент уже известен (и, следовательно, ограничения просто действуют как желе-монады, а не как полномасштабные ограничения). Поэтому он использует тот же алгоритм, что и решение Pyth от @ Maltysen, что, вероятно, является самым простым способом решения этой проблемы с использованием типичных примитивов игры в гольф. (Интересно, что решение «просто заявить о проблеме» в моем другом ответе было бы короче, если бы не ошибки / недостатки в интерпретаторе брахилога, несмотря на то, что он не использовал примитивы игры в гольф. Однажды мне нужно написать «улучшенный брахилог») чтобы получить хорошее решение для такого рода проблем; как говорят языки игры в гольф, Brachylog действительно очень многословен.)
Программа состоит из генератора и обертки вокруг него. Во-первых, вот объяснение генератора:
Это почти решает проблему, но мы в конечном итоге генерируем много разделов по много раз каждый. Итак, нам нужна оболочка для дедупликации решений:
источник
Mathematica, 61 байт
Определяет (рекурсивный) унарный оператор,
±
который возвращает список разделов.источник
Pyth - 17 байт
Принимает все перестановки простой факторизации, затем разбивает каждое из них, а затем производит все разбиения, а затем сохраняет только отдельные разбиения.
Тестовый пакет .
источник
Python 2, 70 байт
Выводит список отсортированных списков. Например
f(20)
есть[[2, 2, 5], [2, 10], [4, 5], [20]]
.источник
O(n)
и сравнение с конкурентом Python 2 может быть болееO(n^4)
стильным - в то время как f (998) может привести к потере памяти или аппаратному обеспечению в процессе работы время, составляющее 80 дней с другим алгоритмом, этот здесь сходится после прибл. 7 миллисекунд на моей машине, чтобы дать результат[[2, 499], [998]]
. ИМО проблема может быть более , что для останавливается над Python 3 код ... счастлив играть в гольф :-)N > 998
RecursionError: maximum recursion depth exceeded in comparison
O(n^4)
даже достаточно для моей отправки на Python2: D Учитывая тестовый пример 998, мой код будет выполняться 9 раз и(n+r-1)! / r! / (n-1)!
каждый раз вычислять количество кортежей, гдеr
линейно растет от 2, а n равно9 - 2
. Но, эй, по крайней мере, вам не нужно настраивать предел рекурсии ...Желе ,
141311 байтПопробуйте онлайн!
Я был уверен, что решение Jelly @ Dennis можно улучшить. К сожалению, мне не удалось побить рекорд Brachylog, но мне удалось связать его. Обновление : с помощью @Dennis, теперь улучшено; Я думаю, желе забирает корону.
Эта программа невероятно неэффективна, имея производительность O (2 n 2 ) (именно поэтому в приведенном выше тестовом примере она показана для входа 4). Это завершается быстро на 4, очень медленно на 5, и может быть практически невозможно работать для больших чисел.
Интересно, что Brachylog был улучшен путем перехода от решения, описывающего проблему (в котором Brachylog хорош), к решению, в котором использовался алгоритм, основанный на факторизации входных данных (что хорошо умеет Jelly); Между тем, решение Jelly было улучшено, отойдя от его сильных сторон и вернувшись к решению, которое просто описывает проблему.
Объяснение:
Поскольку выходные данные
Ḋx
сортируются, каждая подпоследовательность также должна быть отсортирована, и, таким образом, нам не нужно сортировать их по отдельности. Таким образом, «один и тот же вывод в разных порядках является дублирующей» частью проблемы, а «все значения в выходных данных> 1» являются частью проблемы, решаемой генерацией. Кроме того, что мы в основном делаем здесь, это «найти все списки, для которыхP=³
», что мы делаем (невероятно неэффективно), генерируя все рассматриваемые списки и затем отфильтровывая неправильные.(Понятно, что кому-то нужно изобрести гибрид Jelly и Brachylog, плюс действительно хороший решатель ограничений, чтобы мы могли написать что-то вроде строк
{P=³}~
плюс некоторый код дедупликации и решить программу в гораздо более короткой длине. хотя на некотором расстоянии.)источник
2r
Может статьḊ
, иP=³$$
может статьP=¥
.P=¥
не работает, когда я пробую это в интерпретаторе, хотя я не совсем уверен, почему (по логике, это должно сработать, и это было одной из вещей, которые я пробовал при написании поста; я просто попробовал это снова, чтобы убедиться, это определенно не делает то, что я ожидал).Ḋ
хотя, так что, я думаю, есть наше однобайтовое сохранение :-)µ
с ,¹
а также, как иµ
делает повторный диапазон новый левый аргумент.³
а не¹
только для разнообразия.)JavaScript (ES6),
7467 байтНепосредственно решает проблему рекурсивно: для каждого целого числа m от 2 до n мы берем каждый из разделов n / m с минимальным элементом m (чтобы избежать дублирования разделов) и добавляем m . (Для любого m, которое не делит n , это дает пустой массив, так как никакое расположение целых чисел не умножается на десятичное число.) Мы определяем базовый случай пустого массива для 1, чтобы избежать бесконечной рекурсии.
источник
Python2,
198191172180 байтПолная программа. Это может быть улучшено, поэтому предложения приветствуются!
Выходы в диапазоне от 1 до 31 (включительно):
источник
4 -> {2, 2}, {4}
, я не вижу такого вывода в вашем журнале.int(math.log(n,2))
, что вызвало это. +2 байта и все будет работать. Благодарность!math
но используетеmath.log
.len(bin(n))-2
корочеint(math.log(n,2))
.Желе , 15 байт
Попробуйте онлайн!
источник
Clojure, 91 байт
Пример работы:
Само значение возвращается как одно число (не a
list
), другие выходят в виде списков. Вn
конце можно заменить на,[n]
чтобы сделать его также последовательностью или(list n)
составить список.источник
Wolfram Language (Mathematica) ,
585652 байтаПопробуйте онлайн!
Адаптировано из моего решения Mathematica для деления делителей . Возвращает
Sequence
из разделов.источник
J 35 байт
Основано на решении сложной задачи факторизации.
Эта версия намного более неэффективна и работает в факториальное время, основанное на числе простых факторов. Создает разделы, генерируя факторические числа.
Попробуйте онлайн! (Не пытайтесь большие значения онлайн!)
объяснение
источник
D, 95 байт
Просто рекурсивное решение. In
g(n,r)
,r
это раздел до сих пор, иn
это значение, которое еще нужно разбить на факторы. Чтобы получить каждый неупорядоченный раздел только один раз, мы сортируем факторыr
по возрастанию. Последний элементr
начинается2
с наименьшего возможного коэффициента и перезаписываетсяn
в каждой копии непосредственно перед каждой операцией вывода.Для
n = 60
, выход будет следующим:Попробуйте онлайн!
источник
void g(T)(T n,T[]r){for(T i=r[0];i*i<=n;i++)n%i0:r;r.back=n;r.writeln;}g(n,[2])
std.stdio
аstd.range
ввод1
ничего не печатать, а не[1]
.D, 109 байт
Попробуйте онлайн!
источник