Factorisation partielle d'un entier positif

23

Une collection d'entiers positifs d_1 d_2 ... d_kest une factorisation d'un entier positif nsi

d_1 * d_2 * ... * d_k = n

Chaque entier positif a une factorisation première unique , mais en général ils ont aussi des factorisations dans lesquelles certains des termes sont composites. Par exemple

12 = 6 * 2 = 4 * 3 = 3 * 2 * 2

Écrivez un programme, une fonction, un verbe ou similaire qui prend en entrée un seul entier positif et retourne ou imprime une liste complète de ses factorisations distinctes. Les factorisations peuvent être produites dans n'importe quel ordre, et leurs termes peuvent être dans n'importe quel ordre, mais il ne doit pas y avoir de permutations mutuelles. Les factorisations peuvent ne pas inclure 1à deux exceptions près: pour l'entrée, nvous pouvez donner la factorisation n*1au lieu de n; et pour l'entrée, 1vous pouvez donner la factorisation 1au lieu de la liste vide.

Vous pouvez supposer que l'entrée sera dans la plage d'un entier 32 bits signé. Si la sortie est une chaîne, il devrait y avoir une distinction claire entre la délimitation des nombres au sein d'une factorisation et la délimitation des factorisations, mais il n'est pas nécessaire (par exemple) que les facteurs soient joints à un *.

Votre code doit être capable de gérer toute entrée valide dans les 10 minutes sur une machine de bureau raisonnable.

Exemples

1                  [[]]
                or [[1]]
                or [[1 1]]

7                  [[7]]
                or [[7 1]]
                or [[1 7]]

12                 [[12] [6 2] [4 3] [2 3 2]]
                or variants

16                 [[2 2 2 2] [2 2 4] [2 8] [4 4] [16]]
                or variants

901800900          a list of 198091 factorisations

1338557220         a list of 246218 factorisations
Peter Taylor
la source
Pouvez-vous afficher la liste des factorisations de 901800900et 1338557220quelque part où nous pouvons les vérifier? Mon code me donne 2048 et 1024 factorisations pour ces nombres, respectivement, et je ne sais pas pourquoi.
Sherlock9
@ Sherlock9, fera ça quand je rentrerai. Ce que je peux faire avec un générateur en ligne, c'est de vous donner une sortie valide pour 5336100 .
Peter Taylor
3
Cela me rappelle un défi ProjectEuler (malheureusement, je ne me souviens pas lequel). Mais là, il fallait compter le nombre de factorisations au lieu de les lister.
flawr
OEIS connexe: A001055
Sherlock9

Réponses:

12

Haskell, 56 octets

_!1=[[]]
i!n=[j:f|j<-[i..n],mod n j<1,f<-j!div n j]
(2!)

(2!)(1338557220::Int)imprime en cinq minutes sur mon ordinateur portable, une fois compilé avec ghc -O3.

Haskell, 62 octets, mais beaucoup plus rapide

i!n|i*i>n=[[n]]|0<1=[i:f|mod n i<1,f<-i!div n i]++(i+1)!n
(2!)

(2!)(1338557220::Int)imprime en un quart de seconde sur mon ordinateur portable, une fois compilé avec ghc -O3.

Anders Kaseorg
la source
Comment puis-je tester cela? ghcme donne Parse error: naked expression at top levelet me ghcidonneparse error on input `='
Peter Taylor
@PeterTaylor Remplacez la fonction (2!)par le programme main = print ((2!) (1338557220::Int)), compilez avec ghc -O3 factor.hset exécutez avec ./factor.
Anders Kaseorg
7

Pyth, 29 octets

Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2

M                                def g(G, H):
                   @H2             square root of H
                  S                1-indexed range up to floor
                 >    tG           all but first G − 1 elements
            f                      filter for elements T such that:
              %HT                    H mod T
             !                       is false (0)
   m                               map for elements d:
       gd/Hd                         g(d, H/d)
    +Ld                              prepend d to each element
  a                     ]]H        append [[H]]
 s                                 concatenate
                           g2Q   print g(2, input)

Essayez-le en ligne

Fonctionne en vingt secondes 1338557220sur mon ordinateur portable.

Anders Kaseorg
la source
@PeterTaylor La manière habituelle: pyth factor.pyth(ou pyth -c 'Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2'), fournissant 16sur stdin. Assurez-vous que vous utilisez une version actuelle de Pyth; implicite a Qété ajouté en mars. Je ne peux pas imaginer comment vous pourriez obtenir la division par zéro, cependant.
Anders Kaseorg
Arrrrgh. J'utilisais à la "place de ', et bash étendait le !%à autre chose.
Peter Taylor
6

Python , 252 313 312 311 145 141 137 135 103 84 83 83 octets

Ceci est largement basé sur la réponse Pyth d'Anders Kaseorg . Toutes les suggestions de golf sont les bienvenues. Essayez-le en ligne!

Edit: 19 octets joués grâce à Dennis. Correction d'une faute de frappe dans le code et ajout d'un lien TIO.

g=lambda n,m=2:[[n]]+[j+[d]for d in range(m,int(n**.5)+1)if n%d<1for j in g(n/d,d)]

Non golfé:

def g(n, m=2):
    a = [[n]]
    s = int(n**.5) + 1
    for d in range(m, s):
        if n%d == 0:
            for j in g(n/d, d):
                a.append([d]+j)
    return a
Sherlock9
la source
1
**.5se débarrasse de l'importation.
Dennis
4

JavaScript (ES6), 83 octets

f=(n,a=[],m=2,i=m)=>{for(;i*i<=n;i++)n%i<1&&f(n/i,[...a,i],i);console.log(...a,n)}

J'ai seulement emprunté le truc de racine carrée de @ AndersKaseorg car il a fini par me faire gagner des octets dans l'ensemble. Imprime 1pour une entrée de 1, sinon n'imprime pas 1s.

Neil
la source
1

Ruby 1.9+, 87 89 87 octets

Cette réponse est basée sur la réponse Pyth d'Anders Kaseorg . Ce code ne fonctionne que pour les versions après Ruby 1.9, car les lambdas stabby ->n'ont été introduits qu'en 1.9. Toutes les suggestions de golf sont les bienvenues.

g=->n,m=2{(m..Math.sqrt(n)).select{|i|n%i<1}.flat_map{|d|g[n/d,d].map{|j|[d]+j}}+[[n]]}

Non golfé:

def g(n, m=2)
  a = [[n]]
  s = (m..Math.sqrt(n))
  t = s.select{|i|n%i<1}
  t.each do |d|
    g[n/d,d].each do |j|
      a.push([d]+j)
    end
  end
  return a
end
Sherlock9
la source
Cela nécessite-t-il une version particulière de Ruby? Avec 1.8.7, je reçois une plainte concernant g[n/d,d]:wrong number of arguments (0 for 1)
Peter Taylor
Apparemment, des lambdas stabby ->ont été introduites dans Ruby 1.9. Je vais modifier la réponse pour afficher le numéro de version requis.
Sherlock9
OK merci. Je suis toujours curieux de savoir g[n/d,d]. g(n/d,d)est plus rétrocompatible.
Peter Taylor
1
Ah, il f[n]faut appeler les lambdas stabby et les lambdas Ruby en général. f(n)et les f nappels nécessitent defet end. Plus d'infos ici et ici
Sherlock9
1

J, 52 octets

[:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:

Pas aussi efficace que cela pourrait l'être car certaines factorisations peuvent être répétées et une passe finale doit être effectuée après le tri de chaque factorisation puis la déduplication.

Essayez-le en ligne! (Mais essayez de garder les valeurs d'entrée faibles).

Sur mon bureau, les horaires sont

   f =: [:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:
   timex 'r =: f 1338557220'
3.14172
   # r
246218
   timex 'r =: f 901800900'
16.3849
   # r
198091

Explication

Cette méthode repose sur la génération de toutes les partitions définies pour les facteurs premiers de l'entier d'entrée n . Les performances sont meilleures lorsque n est sans carré, sinon des factorisations en double seront créées.

[:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:  Input: integer n
                                                  }:  Curtail, forms an empty array
                       q:                             Prime factorization
                     #@                               Length, C = count prime factors
                         _&(                     )    Repeat that many times on x = []
                                 (            )"1       For each row
                                            ~.            Unique
                                         #\@              Enumerate starting at 1
                                       0,                 Prepend 0
                                  ,~"{~                   Append each of those to a
                                                          copy of the row
                               <@                         Box it
                            ;&]                         Set x as the raze of those boxes
                                                      These are now the restricted growth
                                                      strings of order C
    q:                                                Prime factorization
            (    )"$~                                 For each RGS
               /.                                       Partition it
             */                                         Get the product of each block
        /:~@                                            Sort it
      <@                                                Box it
[:~.                                                  Deduplicate
miles
la source