Список всех мультипликативных разбиений n

28

Учитывая положительное число 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}
orlp
источник

Ответы:

6

Брахилог , 16 байт

>~l:{1<}a.*?,.=o

Это функция (не полная программа), которая принимает положительное число в качестве входных данных и генерирует все его мультипликативные разбиения. (Я также избегал использования каких-либо основных встроенных факторов факторизации в этом решении, в основном потому, что я не был уверен, что они помогут; в какой-то момент я мог бы попробовать и более сложное решение).

Попробуйте онлайн! (Вокруг этой функции был добавлен дополнительный код, чтобы превратить ее в полноценную программу; если вы предоставите функцию, показанную выше, для TIO напрямую, она запустит функцию, но нигде не распечатает свой вывод, что бесполезно в качестве демонстрации .)

Эта программа действительно разочаровывает меня, потому что большая часть ее работает вокруг ошибок в интерпретаторе брахилога и недостатков в его спецификации, а не на самом деле решения проблемы; но переводчик такой, какой он есть. (Даже с такой программой интерпретатор использует гораздо больше памяти, чем логически, и падает из-за истощения памяти, но, к счастью, при небольших проблемах ему удается сначала получить желаемый результат.) В гипотетической «идеальной версии Брахилога» Вы могли бы просто написать ~*.o.:{>1}a,, что было бы на 4 байта короче, но мне нужно было добавить дополнительные ограничения, чтобы немного помочь интерпретатору. (Мне не очень нравится Brachylog, и я бы предпочел придерживаться Prolog, но для работы программы требовались похожие подсказки, а писать их было гораздо дольше. Так что Brachylog так и есть.)

Объяснение:

Как обычно, программа на брахилоге представляет собой набор ограничений; по умолчанию первое ограничение ограничивает входные данные в отношении неизвестного (который я назову A ), второе ограничение ограничивает A в отношении второго неизвестного B и так далее, пока мы не достигнем результата. Некоторые символы, например {}, могут изменить этот общий поток, поэтому я использую другой набор букв (например, X / Y ) для представления неизвестных во вложенных предикатах.

>       A is smaller than the input
~l      B has length A
  1<    X is 1, Y is larger
:{1<}a  For each element X of B, it corresponds to an element Y of C
.       C, the output, and D are all identical
*       E is the product of D's elements
?       E, the input, and F are all identical
,       There's no constraint between F and G
.       G, the output, and H are all identical
=       H and I are identical, and need to be evaluated early
o       The output can be produced by sorting I

До сих пор неясно, как работает программа, поэтому давайте попробуем немного упростить ограничения. C , D , G , H и I одинаковы (и равны выходу). E и F также одинаковы (и равны входу). Таким образом, наши ограничения сводятся к следующему:

  • A - это длина B и выхода, и она меньше, чем вход.
  • B состоит из всех 1 и не особенно полезен (он является частью программы просто потому, что в существующем интерпретаторе брахилога :{1<}aтребуется, чтобы его левый аргумент имел ограниченную длину, иначе интерпретатор входит в бесконечный цикл).
  • Выходные данные полностью состоят из чисел, превышающих 1 (т.е. больше, чем соответствующий элемент B ).
  • Произведение элементов выхода равно входу.
  • Вывод остается неизменным путем сортировки (т.е. в порядке сортировки).

Между прочим, я не указал явно, что все элементы вывода являются целыми числами, что может показаться необходимым; тем не менее, решатель ограничений Brachylog не может обрабатывать нецелые числа, поэтому он будет удобно создавать только те решения, которые включают целые числа.

Ясно, что «длина выходного сигнала меньше входного» будет истинной всякий раз, когда выходной сигнал является мультипликативным разделом входного сигнала (потому что 2 x > x для всех неотрицательных x , т.е. положительных 2 x ). Таким образом, мы можем игнорировать это ограничение; это только для того, чтобы дать интерпретатору брахилога рабочую стратегию для оценки программы. Другие ограничения (то, что выходные данные отсортированы, что его произведение является входным, и что все его элементы больше 1) являются определением мультипликативного разбиения, и, следовательно, эта функция в основном является прямой реализацией вопроса.


источник
6

Брахилог 1, 14 байтов

:{$pp~c:*ao}fd

Попробуйте онлайн!

Brachylog 2, 11 10 байт, языковые проблемы постдат

{ḋp~c×ᵐo}ᵘ

Попробуйте онлайн!

Maltysen ответил на этот вопрос в 17 байтах Pyth, поэтому я предложил 16-байтовое решение Brachylog, которое работало путем перевода спецификации вопроса в Brachylog. Пока я этим занимался, Деннис написал 15-байтовое решение Jelly. Так что мне пришлось уменьшить до 14 байтов. Это функция, которая принимает входные данные в качестве аргумента и возвращает список всех разделов (а не генератор, как в моем другом решении).

Через некоторое время после того, как я написал этот ответ, нам с Деннисом удалось совместными усилиями получить решение Jelly до 11 байтов. Оказывается, вышла новая версия Brachylog с более кратким синтаксисом; это откладывает вызов, так что фактически не считается, но он может управлять 11-байтовым общим количеством слишком много, как только он выпущен; более поздние пересмотры языка (вдохновленные другими проблемами) могут составить всего 10, как показано здесь. Две программы идентичны, с единственным отличием в синтаксисе.

В отличие от моего другого решения, которое не использовало много «примитивов для игры в гольф», а скорее прямо указывало на проблему, оно игнорирует почти всю мощь ограничений брахилога и вместо этого производит наилучшее впечатление от Jelly, выписывая цепочку ограничений, для которых левый аргумент уже известен (и, следовательно, ограничения просто действуют как желе-монады, а не как полномасштабные ограничения). Поэтому он использует тот же алгоритм, что и решение Pyth от @ Maltysen, что, вероятно, является самым простым способом решения этой проблемы с использованием типичных примитивов игры в гольф. (Интересно, что решение «просто заявить о проблеме» в моем другом ответе было бы короче, если бы не ошибки / недостатки в интерпретаторе брахилога, несмотря на то, что он не использовал примитивы игры в гольф. Однажды мне нужно написать «улучшенный брахилог») чтобы получить хорошее решение для такого рода проблем; как говорят языки игры в гольф, Brachylog действительно очень многословен.)

Программа состоит из генератора и обертки вокруг него. Во-первых, вот объяснение генератора:

$pp~c:*ao  ḋp~c×ᵐo
$p         ḋ        Prime factor decomposition of the input
  p         p       Generate all permutations
   ~c        ~c     Generate all inverse concatenations (i.e. partitions)
     :*a       ×ᵐ   Take the product of each list element in each partition
        o        o  Sort each partition

Это почти решает проблему, но мы в конечном итоге генерируем много разделов по много раз каждый. Итак, нам нужна оболочка для дедупликации решений:

:{…}fd
:{…}f     Convert generator to list
     d    Remove duplicate elements

{…}ᵘ      Convert generator to list of unique elements

источник
Почему бы не отредактировать свой ответ?
вниз
3
@Downgoat: два ответа используют совершенно разные подходы; алгоритмы разные, используемые языковые функции в основном независимы и тому подобное. Не имеет смысла заменять старый на новый (и я вполне мог бы опубликовать новый, даже если бы он был длиннее). Эта мета-публикация предполагает, что публикация отдельных ответов предпочтительнее в такой ситуации.
1
Я не знаю, знаете ли вы это, но вы можете получить вывод, установив аргумент TIO в качестве переменной (то есть заглавной буквы). Например .
фатализировать
5

Mathematica, 61 байт

±1={{}}
±n_:=Union@@(Sort/@Append[n/#]/@±#&/@Most@Divisors@n)

Определяет (рекурсивный) унарный оператор, ±который возвращает список разделов.

Мартин Эндер
источник
Разве Mathematica не требует точки с запятой в конце?
Павел
@Pavel no, точка с запятой просто подавляет вывод в интерактивной записной книжке. Спасибо за указание на это, кстати, я случайно оставил точку с запятой в конце.
Мартин Эндер
4

Pyth - 17 байт

Принимает все перестановки простой факторизации, затем разбивает каждое из них, а затем производит все разбиения, а затем сохраняет только отдельные разбиения.

{mS-*Md1s./M.p+1P

Тестовый пакет .

Maltysen
источник
4

Python 2, 70 байт

f=lambda n,k=2,l=[]:n/k and(n%k<1)*f(n/k,k,l+[k])+f(n,k+1,l)or 1/n*[l]

Выводит список отсортированных списков. Например f(20)есть [[2, 2, 5], [2, 10], [4, 5], [20]].

XNOR
источник
Поскольку встроенный целочисленный тип Python не имеет ограничений, с плавающей запятой это неприемлемое решение, поскольку неточности могут нарушить ответ для слишком больших входных данных.
orlp
@orlp Хорошо, тогда вернемся к Python 2.
xnor
TL; DR Я думаю, что 998 не слишком большой ввод ;-) IMO - действительно классный код, больше похожий на задержку, O(n)и сравнение с конкурентом Python 2 может быть более O(n^4)стильным - в то время как f (998) может привести к потере памяти или аппаратному обеспечению в процессе работы время, составляющее 80 дней с другим алгоритмом, этот здесь сходится после прибл. 7 миллисекунд на моей машине, чтобы дать результат [[2, 499], [998]]. ИМО проблема может быть более , что для останавливается над Python 3 код ... счастлив играть в гольф :-)N > 998RecursionError: maximum recursion depth exceeded in comparison
Dilettant
@Dilettant Не уверен, что O(n^4)даже достаточно для моей отправки на Python2: D Учитывая тестовый пример 998, мой код будет выполняться 9 раз и (n+r-1)! / r! / (n-1)!каждый раз вычислять количество кортежей, где rлинейно растет от 2, а n равно 9 - 2. Но, эй, по крайней мере, вам не нужно настраивать предел рекурсии ...
Yytsi
@TuukkaX Предостережение: я не анализировал код, просто просмотрел и сравнил время выполнения между двумя кандидатами для некоторого N до 41, а затем подумал, что я просто фиксирую комментарий ;-) Стеки и рекурсия часто упрощаются, но потом Позвоните, чтобы узнать, насколько глубоки вопросы в неприятных ситуациях ... надеюсь, я придумал это достаточно нечетко для объема исследований, которые были проведены.
Дилетант
3

Желе , 14 13 11 байт

Ḋx³ŒPQP=¥Ðf

Попробуйте онлайн!

Я был уверен, что решение Jelly @ Dennis можно улучшить. К сожалению, мне не удалось побить рекорд Brachylog, но мне удалось связать его. Обновление : с помощью @Dennis, теперь улучшено; Я думаю, желе забирает корону.

Эта программа невероятно неэффективна, имея производительность O (2 n 2 ) (именно поэтому в приведенном выше тестовом примере она показана для входа 4). Это завершается быстро на 4, очень медленно на 5, и может быть практически невозможно работать для больших чисел.

Интересно, что Brachylog был улучшен путем перехода от решения, описывающего проблему (в котором Brachylog хорош), к решению, в котором использовался алгоритм, основанный на факторизации входных данных (что хорошо умеет Jelly); Между тем, решение Jelly было улучшено, отойдя от его сильных сторон и вернувшись к решению, которое просто описывает проблему.

Объяснение:

Ḋx³ŒPQP=¥Ðf
Ḋ              List of integers from 2 to the input (apparently undocumented)
 x³            Make a number of copies of each that's equal to the input
   ŒP          Take all (possibly noncontiguous) subsequences of that list (!)
     Q         Remove duplicates
         Ðf    Filter, keeping elements where:
      P=         their product is equal to {the original input, by default}
        ¥      Parse preceding two links as a unit

Поскольку выходные данные Ḋxсортируются, каждая подпоследовательность также должна быть отсортирована, и, таким образом, нам не нужно сортировать их по отдельности. Таким образом, «один и тот же вывод в разных порядках является дублирующей» частью проблемы, а «все значения в выходных данных> 1» являются частью проблемы, решаемой генерацией. Кроме того, что мы в основном делаем здесь, это «найти все списки, для которых P=³», что мы делаем (невероятно неэффективно), генерируя все рассматриваемые списки и затем отфильтровывая неправильные.

(Понятно, что кому-то нужно изобрести гибрид Jelly и Brachylog, плюс действительно хороший решатель ограничений, чтобы мы могли написать что-то вроде строк {P=³}~плюс некоторый код дедупликации и решить программу в гораздо более короткой длине. хотя на некотором расстоянии.)


источник
Пожалуйста, кто-нибудь найдет здесь символ сбережений. Мне бы понравилась «байтовая война», в которой записи продолжают становиться на один байт каждый раз короче. Здесь потрачено достаточно байтов на структурные части программы, поэтому кажется, что это может быть невозможно.
1
Хех, я как раз собирался опубликовать что-то поразительно похожее. (Должен освежить чаще.) 2rМожет стать , и P=³$$может стать P=¥.
Деннис
P=¥не работает, когда я пробую это в интерпретаторе, хотя я не совсем уверен, почему (по логике, это должно сработать, и это было одной из вещей, которые я пробовал при написании поста; я просто попробовал это снова, чтобы убедиться, это определенно не делает то, что я ожидал). хотя, так что, я думаю, есть наше однобайтовое сохранение :-)
1
Не обратил внимания на еще одну деталь. Вы должны были бы заменить µс , ¹а также, как и µделает повторный диапазон новый левый аргумент.
Деннис
О Конечно. Так что теперь мы до 11 с гораздо меньшим количеством персонажей, что заставляет меня чувствовать себя намного лучше. (Я использовал, ³а не ¹только для разнообразия.)
2

JavaScript (ES6), 74 67 байт

f=(n,m=2,a=[])=>n>1?m>n?[]:f(n,m+1,a).concat(f(n/m,m,[...a,m])):[a]

for (var i = 1; i < 31; i++) console.log(JSON.stringify(f(i)));

Непосредственно решает проблему рекурсивно: для каждого целого числа m от 2 до n мы берем каждый из разделов n / m с минимальным элементом m (чтобы избежать дублирования разделов) и добавляем m . (Для любого m, которое не делит n , это дает пустой массив, так как никакое расположение целых чисел не умножается на десятичное число.) Мы определяем базовый случай пустого массива для 1, чтобы избежать бесконечной рекурсии.

ETHproductions
источник
1

Python2, 198 191 172 180 байт

from itertools import*
n=input()
for i in range(2,len(bin(n))):
 for P in combinations_with_replacement(range(2,n),i):
  if reduce(lambda a,b:a*b,P)==n:print(P)
print[(n,),()][n<2]

Полная программа. Это может быть улучшено, поэтому предложения приветствуются!

  • @FlipTack сэкономил 9 байт!
  • @orlp сэкономил 19 байт!

Выходы в диапазоне от 1 до 31 (включительно):

(1,)
(2,)
(3,)
(2, 2), (4,)
(5,)
(2, 3), (6,)
(7,)
(2, 4), (2, 2, 2), (8,)
(3, 3), (9,)
(2, 5), (10,)
(11,)
(2, 6), (3, 4), (2, 2, 3), (12,)
(13,)
(2, 7), (14,)
(3, 5), (15,)
(2, 8), (4, 4), (2, 2, 4), (2, 2, 2, 2), (16,)
(17,)
(2, 9), (3, 6), (2, 3, 3), (18,)
(19,)
(2, 10), (4, 5), (2, 2, 5), (20,)
(3, 7), (21,)
(2, 11), (22,)
(23,)
(2, 12), (3, 8), (4, 6), (2, 2, 6), (2, 3, 4), (2, 2, 2, 3), (24,)
(5, 5), (25,)
(2, 13), (26,)
(3, 9), (3, 3, 3), (27,)
(2, 14), (4, 7), (2, 2, 7), (28,)
(29,)
(2, 15), (3, 10), (5, 6), (2, 3, 5), (30,)
(31,)
Yytsi
источник
Это вообще работает? Имеется тестовый пример 4 -> {2, 2}, {4}, я не вижу такого вывода в вашем журнале.
Borsunho
@Borsunho Когда я возвращаю старую версию, я забыл добавить +1 к int(math.log(n,2)), что вызвало это. +2 байта и все будет работать. Благодарность!
Yytsi
Вы не импортировали, mathно используете math.log.
orlp
@ или у меня есть ...? На третьей строчке.
Yytsi 26.12.16
@TuukkaX Извините, я только посмотрел на самые верхние строки для импорта, поскольку они почти всегда есть ... Как говорится, len(bin(n))-2короче int(math.log(n,2)).
orlp
1

Clojure, 91 байт

(defn f[n](conj(set(for[i(range 2 n):when(=(mod n i)0)j(f(/ n i))](sort(flatten[i j]))))n))

Пример работы:

(map f [20 84])
(#{20 (2 2 5) (4 5) (2 10)} #{(7 12) (2 2 3 7) (2 3 14) (2 2 21) (2 6 7) (6 14) (3 4 7) (3 28) (4 21) (2 42) 84})

Само значение возвращается как одно число (не a list), другие выходят в виде списков. В nконце можно заменить на, [n]чтобы сделать его также последовательностью или (list n)составить список.

NikoNyrh
источник
0

J 35 байт

([:~.]<@/:~@(*//.)"$~#\#:i.@!@#)@q:

Основано на решении сложной задачи факторизации.

Эта версия намного более неэффективна и работает в факториальное время, основанное на числе простых факторов. Создает разделы, генерируя факторические числа.

Попробуйте онлайн! (Не пытайтесь большие значения онлайн!)

объяснение

([:~.]<@/:~@(*//.)"$~#\#:i.@!@#)@q:  Input: integer n
                                 q:  Prime factorization
(                              )@    Operate on them
                              #        Length
                            !@         Factorial
                         i.@           Range [0, i)
                     #\                Range [1, i]
                       #:              Mixed based conversion - Creates factoradic values
     ]                                 Get factors
            (    )"$~                  For each factoradic value
               /.                        Partition the factors based on equal
                                         digits in the factoradic value
             */                          Get the product of each block
        /:~@                             Sort it
      <@                                 Box it
 [:~.                                  Deduplicate
миль
источник
0

D, 95 байт

void g(int n,int[]r){for(int i=r[0];i*i<=n;i++)(n%i)?0:g(n/i,i~r);r.back=n;r.writeln;}g(n,[2]);

Просто рекурсивное решение. In g(n,r), rэто раздел до сих пор, и nэто значение, которое еще нужно разбить на факторы. Чтобы получить каждый неупорядоченный раздел только один раз, мы сортируем факторы rпо возрастанию. Последний элемент rначинается 2с наименьшего возможного коэффициента и перезаписывается nв каждой копии непосредственно перед каждой операцией вывода.

Для n = 60, выход будет следующим:

[3, 2, 2, 5]
[2, 2, 15]
[3, 2, 10]
[5, 2, 6]
[2, 30]
[4, 3, 5]
[3, 20]
[4, 15]
[5, 12]
[6, 10]
[60]

Попробуйте онлайн!

Gassa
источник
Используйте шаблоны, Гасса, используйте шаблоны: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])
Zacharý
В любом случае, это даже не правильный ответ, так как вам нужно импортировать, std.stdioа std.rangeввод 1ничего не печатать, а не [1].
Захари