Biorąc pod uwagę liczbę dodatnią n , wypisz wszystkie wyraźne multiplikatywne partycje nw dowolnym dogodnym formacie.

Mnożnikowa partycja n to zbiór liczb całkowitych, wszystkie większe niż jeden, tak że ich iloczynem jest n . Na przykład 20 ma następujące odrębne partycje multiplikatywne:

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

Kolejność nie ma znaczenia, więc 2 * 2 * 5ta sama partycja co 2 * 5 * 2.

Przykłady:

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 bajtów

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

Jest to funkcja (nie pełny program), która przyjmuje na wejściu liczbę dodatnią i generuje wszystkie jej multiplikatywne partycje. (Unikałem także używania jakichkolwiek wbudowanych faktoryzacji głównych w tym rozwiązaniu, głównie dlatego, że nie byłem pewien, czy one pomogą; w pewnym momencie mógłbym również wypróbować bardziej wbudowane rozwiązanie).

Wypróbuj online! (W tym miejscu wokół funkcji dodano dodatkowy kod, aby przekształcić go w pełny program; jeśli podasz funkcję pokazaną powyżej TIO bezpośrednio, uruchomi ona funkcję, ale nigdzie nie wydrukuje swoich wyników, co jest raczej bezużyteczne jako demonstracja .)

Ten program naprawdę mnie rozczarowuje, ponieważ w dużej mierze pracuje nad błędami interpretera Brachylog i brakami w specyfikacji, a nie w rzeczywistości rozwiązuje problem; ale tłumacz jest tym, czym jest. (Nawet przy takim programie interpreter zużywa znacznie więcej pamięci, niż to logicznie powinno, i ulega awarii z powodu wyczerpania pamięci, ale na szczęście przy małych problemach najpierw udaje mu się uzyskać pożądane wyjście.) W hipotetycznej „idealnej wersji Brachylog” możesz po prostu pisać ~*.o.:{>1}a,, czyli o 4 bajty krócej, ale musiałem dodać dodatkowe ograniczenia, aby nieco pomóc tłumaczowi. (Nie bardzo lubię Brachylog i wolałbym trzymać się Prologa, ale potrzebowałem podobnych wskazówek, aby program działał i są o wiele dłużej pisać. Więc Brachylog to jest.)

Wyjaśnienie:

Jak zwykle program Brachylog jest zbiorem ograniczeń; domyślnie pierwsze ograniczenie ogranicza dane wejściowe do nieznanego (które nazywam A ), drugie ograniczenie ogranicza A do drugiego nieznanego B i tak dalej, aż osiągniemy wynik. Niektóre znaki, takie jak {}, mogą zmieniać ten ogólny przepływ, więc używam innego zestawu liter (np. X / Y ) do reprezentowania nieznanych w zagnieżdżonych predykatach.

>       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

Nadal nie jest jasne, jak działa program, więc spróbujmy nieco uprościć ograniczenia. C , D , G , H i I są takie same (i równe mocy wyjściowej). E i F są również takie same (i równe wejściowi). Nasze ograniczenia sprowadzają się do tego:

• A jest długością B i wyjściową i jest mniejsza niż wejściowa.
• B składa się ze wszystkich 1 i nie jest szczególnie użyteczny (jest częścią programu po prostu dlatego, że w istniejącym interpreterze Brachylog :{1<}apotrzebuje lewego argumentu, aby mieć ograniczoną długość, inaczej interpreter przejdzie w nieskończoną pętlę).
• Wynik składa się całkowicie z liczb większych niż 1 (tj. Większych niż odpowiedni element B ).
• Iloczyn elementów wyjścia jest równy nakładowi.
• Wyjście pozostaje niezmienione poprzez sortowanie (tj. W posortowanej kolejności).

Nawiasem mówiąc, nie określiłem wyraźnie, że wszystkie elementy wyniku są liczbami całkowitymi, co może wydawać się wymagane; jednak narzędzie do rozwiązywania ograniczeń Brachylog nie jest w stanie obsłużyć liczb całkowitych, więc wygodnie wygeneruje tylko rozwiązania obejmujące liczby całkowite.

Oczywiście „długość danych wyjściowych jest mniejsza niż wartość wejściowa” będzie prawdą, ilekroć dane wyjściowe są multiplikatywną partycją danych wejściowych (ponieważ 2 ^x > x dla wszystkich nieujemnych x , tj. Dodatnia 2 ^x ). Możemy więc zignorować to ograniczenie; jest tylko po to, aby dać tłumaczowi Brachylog działającą strategię oceny programu. Inne ograniczenia (że dane wyjściowe są posortowane, że ich iloczyn jest danymi wejściowymi i że wszystkie jego elementy są większe niż 1) są definicją partycji multiplikatywnej, a zatem funkcja ta jest w zasadzie tylko bezpośrednią implementacją pytania.

Brachylog 1,14 bajtów

:{$pp~c:*ao}fd

Wypróbuj online!

Brachylog 2, 11 10 bajtów, wyzwanie dotyczące postdatacji języka

{ḋp~c×ᵐo}ᵘ

Wypróbuj online!

Maltysen odpowiedział na to pytanie w 17 bajtach Pytha, więc wymyśliłem 16-bajtowe rozwiązanie Brachylog, które działało, tłumacząc specyfikację pytania na Brachylog. Podczas gdy to robiłem, Dennis napisał 15-bajtowe rozwiązanie Jelly. Musiałem więc zejść do 14 bajtów. Jest to funkcja, która przyjmuje dane wejściowe jako argument i zwraca listę wszystkich partycji (zamiast generatora, jak w moim innym rozwiązaniu).

Jakiś czas po tym, jak napisałem tę odpowiedź, udało nam się wspólnie z Dennisem sprowadzić rozwiązanie Jelly do 11 bajtów. Okazuje się, że pojawiła się nowa wersja Brachylog ze składnią terser; odkłada wyzwanie na później, więc tak naprawdę się nie liczy, ale może zarządzać zbyt 11-bajtową sumą zaraz po wydaniu; późniejsze wersje języka (zainspirowane innymi wyzwaniami) mogą spaść nawet do 10, jak widać tutaj. Oba programy są identyczne, a jedyną różnicą jest składnia.

W przeciwieństwie do mojego innego rozwiązania, które nie wykorzystywało zbyt wiele „golfowych prymitywów”, ale raczej bezpośrednio określało problem, ten ignoruje prawie całą moc ograniczeń Brachylog i robi swoje najlepsze wrażenia galaretki, pisząc łańcuch ograniczeń, dla których lewy argument jest już znany (a zatem ograniczenia po prostu działają jak galaretowe monady, a nie w pełni). Dlatego używa tego samego algorytmu co rozwiązanie Pyth @ Maltysen, co jest prawdopodobnie najłatwiejszym sposobem rozwiązania tego problemu przy użyciu typowych prymitywów golfowych. (Co ciekawe, rozwiązanie „wystarczy podać problem” w mojej drugiej odpowiedzi byłoby krótsze, gdyby nie błędy / braki w interpretatorze Brachylog, pomimo braku użycia prymitywów golfowych. Pewnego dnia muszę napisać „ulepszony Brachylog” w celu znalezienia dobrego rozwiązania tego rodzaju problemu; w miarę gry w golfa Brachylog jest naprawdę bardzo gadatliwy.)

Program składa się z generatora i wokół niego otoki. Po pierwsze, oto wyjaśnienie generatora:

$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

To prawie rozwiązuje problem, ale ostatecznie generujemy wiele partycji wiele razy. Potrzebujemy więc opakowania do deduplikacji rozwiązań:

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

{…}ᵘ      Convert generator to list of unique elements

Mathematica, 61 bajtów

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

Definiuje (rekurencyjny) jednoargumentowy operator, ±który zwraca listę partycji.

Pyth - 17 bajtów

Pobiera wszystkie permutacje pierwszej faktoryzacji, następnie partycjonuje każdą z nich, a następnie tworzy wszystkie partycje, a następnie zachowuje tylko odrębne partycje.

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

Pakiet testowy .

Python 2, 70 bajtów

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]

Wyświetla listę posortowanych list. Na przykład f(20)jest [[2, 2, 5], [2, 10], [4, 5], [20]].

Galaretka , 14 13 11 bajtów

Ḋx³ŒPQP=¥Ðf

Wypróbuj online!

Byłem całkiem pewien, że rozwiązanie Jelly @ Dennisa można ulepszyć. Niestety nie udało mi się pobić rekordu Brachylog, ale udało mi się go powiązać. Aktualizacja : Z pomocą @Dennis poprawiono go teraz; Chyba Jelly odbiera koronę.

Ten program jest niezwykle nieefektywny, ma wydajność O (2 ^{n 2} ) (dlatego powyższy przypadek testowy pokazuje go dla wejścia 4). Kończy się szybko na 4, bardzo powoli na 5 i może nie być praktycznie możliwe uruchomienie większej liczby.

Co ciekawe, Brachylog został ulepszony, przechodząc od rozwiązania opisującego problem (w którym Brachylog jest dobry) do rozwiązania wykorzystującego algorytm oparty na faktoryzacji danych wejściowych (w którym Jelly jest dobry); tymczasem rozwiązanie Jelly zostało ulepszone poprzez odejście od jego mocnych stron i powrót do rozwiązania, które właśnie opisuje problem.

Wyjaśnienie:

Ḋ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

Ponieważ dane wyjściowe Ḋxsą sortowane, każda podsekwencja musi być również posortowana, a zatem nie musimy sortować ich indywidualnie. Tak więc „ta sama produkcja w różnych rzędach jest duplikatem” części problemu, a „wszystkie wartości w danych wyjściowych to> 1” część problemu, zostaną rozwiązane przez generację. Poza tym w zasadzie robimy tutaj „znajdź wszystkie listy dla których P=³”, co robimy (w niewiarygodnie nieefektywny sposób), generując wszystkie omawiane listy, a następnie filtrując niepoprawne.

(Najwyraźniej ktoś musi wymyślić hybrydę Jelly i Brachylog, a także naprawdę dobry solver ograniczający, abyśmy mogli napisać coś podobnego do {P=³}~kodu deduplikacji i rozwiązać program o wiele krótszej długości. Może to być w pewnej odległości).

JavaScript (ES6), 74 67 bajtów

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

Bezpośrednio rozwiązuje problem rekurencyjnie: dla każdej liczby całkowitej m z 2 do N , weźmiemy każdej z przegród n / m z elementem minimalna liczba m (aby uniknąć powielania partycji) i dołączyć m . (Dla każdego m , który nie dzieli n , daje to pustą tablicę, ponieważ żadne liczby całkowite nie mnożą się do dziesiętnej.) Definiujemy podstawowy przypadek pustej tablicy dla 1 , aby uniknąć nieskończonej rekurencji.

Python2, 198 191 172 180 bajtów

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]

Pełny program. Można to znacznie poprawić, więc sugestie są bardzo mile widziane!

• @FlipTack zapisał 9 bajtów!
• @orlp zapisał 19 bajtów!

Wyjścia z zakresu od 1 do 31 (włącznie):

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

Galaretka , 15 bajtów

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

Wypróbuj online!

Clojure, 91 bajtów

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

Przykładowe przebiegi:

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

Sama wartość jest zwracana jako pojedyncza liczba (nie a list), inne pojawiają się jako listy. Na nkońcu można go zastąpić, [n]aby uczynić go również sekwencją lub (list n)zrobić z niej listę.

Wolfram Language (Mathematica) , 58 56 52 bajtów

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

Wypróbuj online!

Zaadaptowałem z mojego rozwiązania Mathematica do Divisors Divisors Dividing . Zwraca a Sequencepartycji.

J, 35 bajtów

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

Na podstawie rozwiązania ograniczonego czasowo wyzwania faktoryzacji.

Ta wersja jest znacznie bardziej nieefektywna i działa w czasie silnym na podstawie liczby czynników pierwszych. Tworzy partycje, generując liczby czynnikowe.

Wypróbuj online!(Nie próbuj dużych wartości online!)

Wyjaśnienie

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

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

Tylko rekurencyjne rozwiązanie. W g(n,r), rjest jak dotąd partycją i nnadal pozostaje wartość do podziału na czynniki. Aby uzyskać każdą nieuporządkowaną partycję tylko raz, sortujemy czynniki w rkolejności malejącej. Ostatni element rzaczyna się 2jako najmniej możliwy czynnik i zostaje zastąpiony przez nkażdą kopię tuż przed każdą operacją wyjściową.

Dane n = 60wyjściowe są następujące:

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

Wypróbuj online!

D, 109 bajtów

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

Wypróbuj online!