Częściowe faktoryzacje dodatniej liczby całkowitej


23

Zbiór dodatnich liczb całkowitych d_1 d_2 ... d_kjest faktoryzacją dodatniej liczby całkowitej, njeśli

d_1 * d_2 * ... * d_k = n

Każda dodatnia liczba całkowita ma unikalną faktoryzację pierwszą , ale generalnie mają one również faktoryzacje, w których niektóre terminy są złożone. Na przykład

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

Napisz program, funkcję, czasownik lub podobne, które przyjmują jako dane wejściowe jedną dodatnią liczbę całkowitą i zwracają lub drukują pełną listę ich odrębnych faktoryzacji. Rozkłady na czynniki mogą być tworzone w dowolnej kolejności, a ich warunki mogą być w dowolnej kolejności, ale żadne z nich nie powinno być wzajemnymi permutacjami. Faktoryzacje mogą nie obejmować 1dwóch wyjątków: dla danych wejściowych nmożna podać faktoryzację n*1zamiast n; a dla danych wejściowych 1możesz podać faktoryzację 1zamiast pustej listy.

Możesz założyć, że wejście będzie w zakresie 32-bitowej liczby całkowitej ze znakiem. Jeśli dane wyjściowe są w postaci ciągu, powinno być wyraźne rozróżnienie między delimitacją liczb w ramach faktoryzacji i delimitacją faktoryzacji, ale nie jest konieczne (na przykład) łączenie czynników z *.

Twój kod powinien być w stanie obsłużyć wszelkie prawidłowe dane wejściowe w ciągu 10 minut na rozsądnym komputerze stacjonarnym.

Przykłady

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

Czy możesz opublikować listę faktoryzacji 901800900i 1338557220gdzieś, gdzie możemy je sprawdzić? Mój kod podaje mi odpowiednio 2048 i 1024 faktoryzacji dla tych liczb i nie jestem pewien, dlaczego.
Sherlock9

@ Sherlock9, zrobię to, kiedy wrócę do domu. To, co mogę zrobić z generatorem online, to dać ci prawidłowe wyjście dla 5336100 .
Peter Taylor

3
To przypomina mi wyzwanie ProjectEuler (niestety nie pamiętam, które). Ale tam trzeba było policzyć liczbę faktoryzacji zamiast ich wyszczególnienia.
flawr

Powiązany OEIS: A001055
Sherlock9

Odpowiedzi:


12

Haskell, 56 bajtów

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

(2!)(1338557220::Int)drukuje w ciągu pięciu minut na moim laptopie po skompilowaniu ghc -O3.

Haskell, 62 bajty, ale znacznie szybciej

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)drukuje w kwadrans na moim laptopie, po skompilowaniu ghc -O3.


Jak to przetestować? ghcdaje mi Parse error: naked expression at top leveli ghcidajeparse error on input `='
Peter Taylor

@PeterTaylor Zamień funkcję (2!)na program main = print ((2!) (1338557220::Int)), skompiluj ghc -O3 factor.hsi uruchom z ./factor.
Anders Kaseorg

7

Pyth, 29 bajtów

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)

Wypróbuj online

Działa za dwadzieścia sekund 1338557220na moim laptopie.


@PeterTaylor Zwykły sposób: pyth factor.pyth(lub pyth -c 'Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2'), podając 16na standardowe wejście . Upewnij się, że używasz aktualnej wersji Pyth; domniemany Qzostał dodany w marcu. Nie mogę sobie jednak wyobrazić, jak można uzyskać podział na zero.
Anders Kaseorg,

Arrrrgh. Używałem "zamiast ', a bash rozwijał !%coś innego.
Peter Taylor

6

Python , 252 313 312 311 145 141 137 135 103 84 83 bajtów

Jest to w dużej mierze oparte na pytaniu Andersa Kaseorga . Wszelkie sugestie dotyczące gry w golfa są mile widziane. Wypróbuj online!

Edycja: 19 bajtów golfowych dzięki Dennisowi. Naprawiono literówkę w kodzie i dodano link 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)]

Nie golfowany:

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

1
**.5pozbywa się importu.
Dennis

4

JavaScript (ES6), 83 bajty

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

Pożyczyłem tylko sztuczkę @ pierwiastka kwadratowego @ AndersKaseorga, ponieważ ostatecznie zaoszczędziło mi bajtów. Drukuje 1dla wejścia 1, w przeciwnym razie nie drukuje 1s.


1

Ruby 1.9+, 87 89 87 bajtów

Ta odpowiedź oparta jest na pytaniu Andersa Kaseorga . Ten kod działa tylko w wersjach po Ruby 1.9, ponieważ stabilne lambdy ->zostały wprowadzone tylko w wersji 1.9. Wszelkie sugestie dotyczące gry w golfa są mile widziane.

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

Nie golfowany:

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

Czy to wymaga konkretnej wersji Ruby? W wersji 1.8.7 otrzymuję skargę na g[n/d,d]:wrong number of arguments (0 for 1)
Peter Taylor,

Najwyraźniej mocne lambdy ->zostały wprowadzone w Ruby 1.9. Zmienię odpowiedź, aby wyświetlić wymagany numer wersji.
Sherlock9

Ok dzięki. Nadal jestem ciekawa g[n/d,d]. g(n/d,d)jest bardziej kompatybilny wstecz.
Peter Taylor

1
Ach, f[n]wymagane jest nazywanie mocnych lambdas i Ruby lambdas w ogóle. f(n)i f npołączenia wymagają defi end. Więcej informacji tutaj i tutaj
Sherlock9

1

J, 52 bajty

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

Nie tak wydajne, jak mogłoby być, ponieważ niektóre czynniki mogą być powtarzane, a po sortowaniu każdej faktoryzacji, a następnie usuwaniu duplikatów, należy wykonać końcowe przejście.

Wypróbuj online! (Ale staraj się utrzymywać małe wartości wejściowe).

Na moim pulpicie są czasy

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

Wyjaśnienie

Ta metoda polega na generowaniu wszystkich ustawionych partycji dla czynników pierwszych wejściowej liczby całkowitej n . Wydajność jest najlepsza, gdy n nie zawiera kwadratów, w przeciwnym razie zostaną utworzone zduplikowane czynniki.

[:~.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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.