Étant donné un nombre positif n , sortez toutes les partitions multiplicatives distinctes de n dans n'importe quel format pratique.

Une partition multiplicative de n est un ensemble d'entiers, tous supérieurs à un, de sorte que leur produit est n . Par exemple, 20 a les partitions multiplicatives distinctes suivantes:

2 * 2 * 5
2 * 10
4 * 5
20

L'ordre n'a pas d'importance, tout 2 * 2 * 5comme la même partition 2 * 5 * 2.

Exemples:

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}

Brachylog , 16 octets

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

C'est une fonction (pas un programme complet) qui prend un nombre positif en entrée et en génère toutes les partitions multiplicatives. (J'ai également évité d'utiliser des facteurs de factorisation principaux dans cette solution, principalement parce que je n'étais pas sûr qu'ils aideraient; je pourrais essayer une solution plus lourde à un moment donné.)

Essayez-le en ligne! (Un code supplémentaire a été ajouté autour de la fonction ici pour en faire un programme complet; si vous fournissez directement la fonction illustrée ci-dessus à TIO, il exécutera la fonction mais n'imprimera sa sortie nulle part, ce qui est en quelque sorte inutile comme démonstration .)

Ce programme me déçoit vraiment, car il fonctionne en grande partie autour des bogues de l'interpréteur Brachylog et des déficiences dans ses spécifications, plutôt que de résoudre réellement le problème; mais l'interprète est ce que c'est. (Même avec le programme comme celui-ci, l'interpréteur utilise beaucoup plus de mémoire qu'il ne devrait logiquement, et se bloque en raison de l'épuisement de la mémoire, mais heureusement, sur de petits problèmes, il parvient à produire la sortie souhaitée en premier.) Dans une hypothétique "version parfaite de Brachylog" vous pourriez simplement écrire ~*.o.:{>1}a,, ce qui serait 4 octets plus court, mais j'avais besoin d'ajouter des contraintes supplémentaires pour aider l'interprète à sortir un peu. (Je n'aime pas vraiment Brachylog, et je préfère m'en tenir à Prolog, mais il avait besoin de conseils similaires pour faire fonctionner le programme et ils sont beaucoup plus longs à écrire. Donc c'est Brachylog.)

Explication:

Comme d'habitude, un programme Brachylog est un ensemble de contraintes; par défaut, la première contrainte contraint l'entrée contre une inconnue (que j'appellerai A ), la deuxième contrainte contraint A contre une deuxième inconnue B , et ainsi de suite jusqu'à ce que nous atteignions la sortie. Certains caractères, tels que {}, peuvent modifier ce flux général, donc j'utilise un autre jeu de lettres (par exemple X / Y ) pour représenter les inconnues dans les prédicats imbriqués.

>       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

On ne sait toujours pas comment fonctionne le programme, alors essayons de simplifier un peu les contraintes. C , D , G , H et I sont tous identiques (et égaux à la sortie). E et F sont également identiques (et égaux à l'entrée). Nos contraintes se résument donc à ceci:

• A est la longueur de B et de la sortie, et est plus petite que l'entrée.
• B se compose de tous les 1, et n'est pas particulièrement utile (il fait partie du programme simplement parce que dans l'interpréteur Brachylog existant, a :{1<}abesoin que son argument de gauche ait une longueur contrainte, ou bien l'interprète entre dans une boucle infinie).
• La sortie est entièrement composée de nombres supérieurs à 1 (c'est-à-dire supérieurs à l'élément correspondant de B ).
• Le produit des éléments de la sortie est égal à l'entrée.
• La sortie est inchangée en la triant (c'est-à-dire dans un ordre trié).

Soit dit en passant, je n'ai pas explicitement spécifié que tous les éléments de la sortie sont des entiers, ce qui peut sembler être requis; cependant, le solveur de contraintes de Brachylog ne peut pas gérer les non-entiers, il ne produira donc que les solutions qui impliquent des entiers.

De toute évidence, "la longueur de la sortie est plus petite que l'entrée" va être vraie chaque fois que la sortie est une partition multiplicative de l'entrée (car 2 ^x > x pour tous les x non négatifs , c'est-à-dire 2 ^x positifs ). Nous pouvons donc ignorer cette contrainte; il n'est là que pour donner à l'interprète Brachylog une stratégie de travail pour évaluer le programme. Les autres contraintes (que la sortie soit triée, que son produit soit l'entrée et que ses éléments soient tous supérieurs à 1) sont la définition d'une partition multiplicative, et donc cette fonction n'est fondamentalement qu'une implémentation directe de la question.

Brachylog 1, 14 octets

:{$pp~c:*ao}fd

Essayez-le en ligne!

Brachylog 2, 11 10 octets, défi de postdates de langue

{ḋp~c×ᵐo}ᵘ

Essayez-le en ligne!

Maltysen a répondu à cette question en 17 octets de Pyth, donc j'ai trouvé une solution Brachylog de 16 octets qui a fonctionné en traduisant la spécification de la question en Brachylog. Pendant que je faisais cela, Dennis a écrit une solution Jelly de 15 octets. J'ai donc dû descendre à 14 octets. Il s'agit d'une fonction qui prend l'entrée en argument et renvoie une liste de toutes les partitions (plutôt qu'un générateur, comme avec mon autre solution).

Quelque temps après avoir écrit cette réponse, Dennis et moi avons réussi à réduire la solution Jelly à 11 octets. Il s'avère qu'il existe une nouvelle version de Brachylog, avec une syntaxe terser; il est postérieur au défi, donc ne compte pas vraiment, mais il pourrait gérer à peu près le total de 11 octets dès sa sortie; les révisions ultérieures de la langue (inspirées d'autres défis) peuvent aller jusqu'à 10, comme on le voit ici. Les deux programmes sont identiques, la seule différence étant la syntaxe.

Contrairement à mon autre solution, qui n'utilisait pas beaucoup les "primitives de golf" mais énonçait plutôt le problème directement, celle-ci ignore à peu près toute la puissance des contraintes Brachylog et fait plutôt sa meilleure impression Jelly, écrivant une chaîne de contraintes pour laquelle l'argument de gauche est déjà connu (et donc les contraintes agissent simplement comme des monades Jelly plutôt que des contraintes à part entière). Il utilise donc le même algorithme que la solution Pyth de @ Maltysen, qui est probablement le moyen le plus simple de résoudre ce problème en utilisant des primitives de golf typiques. (Fait intéressant, la solution "juste énoncer le problème" dans mon autre réponse serait plus courte si ce n'était pour les bugs / déficiences de l'interpréteur Brachylog, malgré son manque d'utilisation des primitives de golf. Un jour, j'ai besoin d'écrire un "Brachylog amélioré" afin d'obtenir une bonne solution pour ce type de problème; comme les langues de golf vont, Brachylog est vraiment très bavard.)

Le programme se compose d'un générateur et d'un wrapper autour de lui. Tout d'abord, voici une explication du générateur:

$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

Cela résout presque le problème, mais nous finissons par générer de nombreuses partitions plusieurs fois chacune. Nous avons donc besoin d'un wrapper pour dédupliquer les solutions:

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

{…}ᵘ      Convert generator to list of unique elements

Mathematica, 61 octets

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

Définit un opérateur unaire (récursif) ±qui renvoie la liste des partitions.

Pyth - 17 octets

Prend toutes les permutations de la factorisation principale, puis partitionne chacune puis produit toutes les partitions, puis ne conserve que des partitions distinctes.

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

Suite de tests .

Python 2, 70 octets

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]

Affiche une liste de listes triées. Par exemple f(20)est [[2, 2, 5], [2, 10], [4, 5], [20]].

Gelée , 14 13 11 octets

Ḋx³ŒPQP=¥Ðf

Essayez-le en ligne!

J'étais assez sûr que la solution Jelly de @ Dennis pourrait être améliorée. Malheureusement, je n'ai pas réussi à battre le record de Brachylog, mais j'ai réussi à égaler. Mise à jour : Avec l'aide de @Dennis, c'est amélioré maintenant; Je suppose que Jelly reprend la couronne.

Ce programme est incroyablement inefficace, avec des performances O (2 ^{n 2} ) (c'est pourquoi le scénario de test ci-dessus le montre pour l'entrée 4). Il se termine rapidement sur 4, très lentement sur 5, et peut ne pas être pratiquement possible de fonctionner pour de plus grands nombres.

Fait intéressant, le Brachylog a été amélioré en passant d'une solution décrivant le problème (auquel Brachylog est bon) à une solution utilisant un algorithme basé sur la factorisation de l'entrée (où Jelly est bon); pendant ce temps, la solution Jelly a été améliorée en s'éloignant de ses points forts et en revenant à une solution qui ne fait que décrire le problème.

Explication:

Ḋ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

Étant donné que la sortie de Ḋxest triée, chaque sous-séquence doit également être triée, et nous n'avons donc pas à les trier individuellement. Ainsi, la «même sortie dans des ordres différents est une partie en double» du problème, et la partie «toutes les valeurs de la sortie sont> 1» du problème, est résolue par la génération. En dehors de cela, ce que nous faisons essentiellement ici est de "trouver toutes les listes pour lesquelles P=³", ce que nous faisons (de manière incroyablement inefficace) en générant toutes les listes en question, puis en filtrant les mauvaises.

(De toute évidence, quelqu'un doit aller inventer un hybride de Jelly et Brachylog, plus un très bon solveur de contraintes, afin que nous puissions écrire quelque chose dans le sens de {P=³}~plus un peu de code de déduplication, et résoudre le programme dans une longueur beaucoup plus courte. Cela pourrait être à une certaine distance, cependant.)

JavaScript (ES6), 74 67 octets

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)));

Résout directement le problème récursivement: pour chaque entier m de 2 à n , nous prenons chacune des partitions de n / m avec un élément minimum de m (pour éviter les partitions en double) et ajoutons m . (Pour tout m qui ne divise pas n , cela donne le tableau vide, car aucun arrangement d'entiers ne se multiplie en décimal.) Nous définissons un cas de base du tableau vide pour 1 afin d'éviter une récursion infinie.

Python2, 198 191 172 172 180 octets

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]

Un programme complet. Cela pourrait être beaucoup amélioré, donc les suggestions sont les bienvenues!

• @FlipTack a sauvé 9 octets!
• @orlp a économisé 19 octets!

Sorties de la plage 1 à 31 (inclus):

(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,)

Gelée , 15 octets

ÆfŒ!ŒṖ€;/P€€Ṣ€Q

Essayez-le en ligne!

Clojure, 91 octets

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

L'exemple s'exécute:

(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})

La valeur elle-même est renvoyée sous la forme d'un nombre unique (pas un list), d'autres sortent sous forme de listes. Le nà la fin pourrait être remplacé par [n]pour en faire une séquence également, ou (list n)pour en faire une liste.

Wolfram Language (Mathematica) , 58 56 52 octets

If[#>1,##&@@#0[#/i,##2,i]~Table~{i,2,Min@##},{##2}]&

Essayez-le en ligne!

Adapté de ma solution Mathematica aux diviseurs diviseurs diviseurs . Renvoie une Sequencedes partitions.

J, 35 octets

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

Basé sur la solution à un défi de factorisation limité dans le temps.

Cette version est beaucoup plus inefficace et fonctionne en temps factoriel en fonction du nombre de facteurs premiers. Crée des partitions en générant des nombres factoriels.

Essayez-le en ligne! (N'essayez pas de grandes valeurs en ligne!)

Explication

([:~.]<@/:~@(*//.)"$~#\#: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

D, 95 octets

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]);

Juste une solution récursive. Dans g(n,r), rest la partition jusqu'à présent, et nest la valeur qui reste à diviser en facteurs. Pour obtenir chaque partition non ordonnée une seule fois, nous trions les facteurs dans run ordre non croissant. Le dernier élément de rcommence 2comme le facteur le moins possible et est remplacé par ndans chaque copie juste avant chaque opération de sortie.

Pour n = 60, la sortie est la suivante:

[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]

Essayez-le en ligne!

D, 109 octets

import std.stdio;void g(T)(T n,T[]r=[2]){if(n-1){for(T i=r[0];i*i<=n;i++)n%i?0:g(n/i,i~r);r[$-1]=n;r.write;}}

Essayez-le en ligne!