Partielle Faktorisierungen einer positiven ganzen Zahl

23

Eine Sammlung von positiven ganzen Zahlen d_1 d_2 ... d_kist eine Faktorisierung einer positiven ganzen Zahl, nwenn

d_1 * d_2 * ... * d_k = n

Jede positive ganze Zahl hat eine eindeutige Primfaktorisierung , aber im Allgemeinen haben sie auch Faktorisierungen, in denen einige der Begriffe zusammengesetzt sind. Z.B

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

Schreiben Sie ein Programm, eine Funktion, ein Verb oder Ähnliches, das eine einzelne positive Ganzzahl als Eingabe verwendet und eine vollständige Liste der einzelnen Faktorisierungen zurückgibt oder ausgibt. Die Faktorisierungen können in beliebiger Reihenfolge erstellt werden, und ihre Begriffe können in beliebiger Reihenfolge angegeben werden, es sollten jedoch keine zwei Permutationen voneinander sein. Faktorisierungen dürfen 1mit zwei Ausnahmen nicht enthalten sein : Für Eingaben können nSie die Faktorisierung n*1anstelle von angeben n; und zur Eingabe 1kann 1anstelle der leeren Liste die Faktorisierung angegeben werden.

Sie können davon ausgehen, dass die Eingabe im Bereich einer vorzeichenbehafteten 32-Bit-Ganzzahl liegt. Wenn es sich bei der Ausgabe um eine Zeichenfolge handelt, sollte klar zwischen der Abgrenzung von Zahlen innerhalb einer Faktorisierung und der Abgrenzung der Faktorisierungen unterschieden werden, es ist jedoch nicht erforderlich (zum Beispiel), dass die Faktoren mit einem verknüpft werden *.

Ihr Code sollte in der Lage sein, alle gültigen Eingaben innerhalb von 10 Minuten auf einem vernünftigen Desktop-Computer zu verarbeiten.

Beispiele

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
quelle
Können Sie die Liste der Faktorisierungen von 901800900und 1338557220irgendwo veröffentlichen, wo wir sie überprüfen können? Mein Code gibt mir 2048 bzw. 1024 Faktorisierungen für diese Zahlen, und ich bin mir nicht sicher, warum.
Sherlock9
@ Sherlock9, werde das machen, wenn ich nach Hause komme. Mit einem Online-Generator kann ich Ihnen eine gültige Ausgabe für 5336100 geben .
Peter Taylor
3
Dies erinnert mich an eine ProjectEuler-Herausforderung (leider weiß ich nicht mehr, welche). Aber da musste man die Anzahl der Faktorisierungen zählen, anstatt sie aufzulisten.
Fehler
Verwandte OEIS: A001055
Sherlock9

Antworten:

12

Haskell, 56 Bytes

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

(2!)(1338557220::Int)druckt in fünf Minuten auf meinem Laptop, wenn er mit kompiliert wird ghc -O3.

Haskell, 62 Bytes, aber viel schneller

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)druckt in einer viertel Sekunde auf meinem Laptop, wenn er mit kompiliert wird ghc -O3.

Anders Kaseorg
quelle
Wie teste ich das? ghcgibt mir Parse error: naked expression at top levelund ghcigibt mirparse error on input `='
Peter Taylor
@PeterTaylor Ersetzen Sie die Funktion (2!)durch das Programm main = print ((2!) (1338557220::Int)), kompilieren Sie mit ghc -O3 factor.hsund führen Sie mit aus ./factor.
Anders Kaseorg
7

Pyth, 29 Bytes

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)

Probieren Sie es online aus

Läuft in zwanzig Sekunden 1338557220auf meinem Laptop.

Anders Kaseorg
quelle
@ PeterTaylor Der übliche Weg: pyth factor.pyth(oder pyth -c 'Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2'), Bereitstellung 16auf stdin. Stellen Sie sicher, dass Sie eine aktuelle Version von Pyth verwenden. implizit Qwurde im März hinzugefügt. Ich kann mir allerdings nicht vorstellen, wie Sie eine Division durch Null bekommen könnten.
Anders Kaseorg
Arrrrgh. Ich habe "stattdessen verwendet 'und bash hat das !%auf etwas anderes erweitert.
Peter Taylor
6

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

Dies basiert größtenteils auf Anders Kaseorgs Pyth-Antwort . Anregungen zum Golfen sind willkommen. Probieren Sie es online!

Edit: 19 Bytes dank Dennis golfen. Ein Tippfehler im Code wurde behoben und ein TIO-Link hinzugefügt.

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

Ungolfed:

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
quelle
1
**.5wird den Import los.
Dennis
4

JavaScript (ES6), 83 Byte

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

Nur @ AndersKaseorgs Quadratwurzel-Trick entlehnt, weil er mir insgesamt Bytes erspart hat. Druckt 1für eine Eingabe von 1, sonst druckt 1s nicht.

Neil
quelle
1

Ruby 1.9+, 87 89 87 Bytes

Diese Antwort basiert auf Anders Kaseorgs Pyth-Antwort . Dieser Code funktioniert nur für Versionen nach Ruby 1.9, da Stabby Lambdas ->erst in 1.9 eingeführt wurden. Anregungen zum Golfen sind willkommen.

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

Ungolfed:

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
quelle
Benötigt das eine bestimmte Version von Ruby? Mit 1.8.7 bekomme ich eine Beschwerde über g[n/d,d]:wrong number of arguments (0 for 1)
Peter Taylor
Offensichtlich ->wurden in Ruby 1.9 stabile Lambdas eingeführt. Ich bearbeite die Antwort, um die erforderliche Versionsnummer anzuzeigen.
Sherlock9
OK danke. Ich bin immer noch neugierig g[n/d,d]. g(n/d,d)ist abwärtskompatibler.
Peter Taylor
1
Ah, das f[n]ist erforderlich, um Stabby Lambdas und Ruby Lambdas im Allgemeinen zu nennen. f(n)und f nAnrufe erfordern defund end. Mehr Infos hier und hier
Sherlock9
1

J, 52 Bytes

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

Nicht so effizient wie es sein könnte, da einige Faktorisierungen möglicherweise wiederholt werden und ein letzter Durchgang nach dem Sortieren jeder Faktorisierung und anschließender Deduplizierung durchgeführt werden muss.

Probieren Sie es online! (Versuchen Sie jedoch, die Eingabewerte klein zu halten).

Auf meinem Desktop sind die Timings

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

Erläuterung

Diese Methode basiert auf der Generierung aller festgelegten Partitionen für die Primfaktoren der Eingabe-Ganzzahl n . Die Leistung ist am besten, wenn n frei von Quadraten ist. Andernfalls werden doppelte Faktorisierungen erstellt.

[:~.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
Meilen
quelle