Wyzwanie polega na wyświetleniu listy wszystkich uporządkowanych partycji (kompozycji (kombinatoryki)) danej dodatniej liczby całkowitej n
. Są wykazy numerów od 1
do n
których suma jest n
. Na przykład przy danych wejściowych n = 4
wynik powinien wynosić:
4
1, 3
3, 1
2, 2
2, 1, 1
1, 2, 1
1, 1, 2
1, 1, 1, 1
Wynik może być w dowolnej kolejności, ale musi zawierać każdą zamówioną partycję jeden raz. Oznacza to, że n = 4
, [1, 1, 2]
, [1, 2, 1]
i [2, 1, 1]
wszystkie muszą być częścią wyniku.
Oto mój własny kod JavaScript, który to osiąga:
function range(n) {
for (var range = [], i = 0; i < n; range.push(++i));
return range;
}
function composition(n) {
return n < 1 ? [[]] : range(n).map(function(i) {
return composition(n - i).map(function(j) {
return [i].concat(j);
});
}).reduce(function(a, b) {
return a.concat(b);
});
}
Gra w golfa, ES6 ( 169 167 119 109 105 89 85 bajtów ):
n=>n?[].concat(...[...Array(n)].map((x,i)=>i+1).map(b=>m(n-b).map(a=>[b,...a]))):[[]]
Odpowiedzi:
Pyth,
76 bajtów7 bajtowe rozwiązanie:
Pyth ma wbudowaną partycję całkowitą
./
, więc 5 z 7 bajtów otrzymuje porządek.Wypróbuj online!
Wyjaśnienie:
6 bajtowe rozwiązanie:
Jeśli masz listę,
./
będzie obliczać z zamówieniami; wszystko, co pozostaje, to ponowne utworzenie numerów list.Wypróbuj online!
Wyjaśnienie:
źródło
Haskell, 37 bajtów
xnor zapisał dwa bajty.
źródło
f n=[a:x|a<-[1..n],x<-f$n-a]
jest krótsze.given positive integer n ... numbers from 1 to n
)f 0=[[]]
tak się składa, że jest to krótszy przypadek podstawowy niżf 1=[[1]]
:)Python, 56 bajtów
Cykliczna rozwiązanie: zamawiane partycje
n
są podział niektóre mniejszei
z0<=i<n
, a następnie pozostałąn-i
jako ostatniego elementu. W przypadku podstawowymn=0
ma tylko pustą partycję.źródło
Python 2, 61 bajtów
To nie jest najkrótsza, ale naprawdę podoba mi się ta metoda, ponieważ jest taka dziwna.
Rekurencyjnie generuje i ocenia
2**(n-1)
ciągi znaków, takie jakdla
n=4
. Te ciągi są przetwarzane na krotki reprezentujące wszystkie partycje. Pomiędzy dwoma dowolnymi 1 jest albo a+
, łączące je w jedną liczbę, albo a,
, dzielące sąsiednie sekcje.źródło
import re
lambda n:map(lambda n:map(len,re.finall('10*',bin(n))),range(1<<n-1,1<<n))
JavaScript (Firefox 30-57), 63 bajty
źródło
f=n=>n<2?[[1]]:f(n-1).map(([n,...a])=>r.push([1+n,...a],[1,n,...a]),r=[])&&r
.Mathematica, 40 bajtów
Wbudowane przez Mathematica partycje całkowite nie dają wszystkich uporządkowanych partycji, więc musimy wygenerować wszystkie możliwe permutacje każdej z nich, a następnie spłaszczyć wynik.
źródło
CJam ,
1714 bajtówWypróbuj online!
Wyjaśnienie
Wiem, że powiedziałem, że używanie produktu kartezjańskiego jest dłuższe, ale ostatecznie znalazłem sposób na bardziej efektywne korzystanie z niego. Myślę, że oba podejścia są interesujące same w sobie, dlatego umieszczam je w osobnych postach.
Nadal opiera się to na założeniu, że możemy wybierać
n
czasy między dołączeniem a1
do bieżącej partycji lub zwiększenie ostatniego elementu bieżącej partycji. W tym rozwiązaniu robimy to, generując 2 n-1 różnych programów, które odpowiadają tym różnym wyborom.źródło
)
”. Więc dodałemed
i przetestowałem. +1 za kreatywne nadużycie błędu.Galaretka ,
76 bajtów-1 bajt dzięki @Dennis (konwertuj z unary
ḅ1
, zamiast sumy dla każdego dla każdegoS€€
)TryItOnline
W jaki sposób?
źródło
Pure Bash, 51
To jest część doskonałej odpowiedzi @ xnor , wykorzystującej wiele poziomów rozszerzeń bash, aby osiągnąć pożądany rezultat:
Ideone.
$a
zawierającej1
następujące po nimn-1
zera.${a//0/{+,']\ $[}1'}
zamienia każde0
na$a
kopie ciągu{+,']\ $[}1'
. Zatem n = 4 otrzymujemy ciąg1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1'
$[
i po tym,],
aby dać$[1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1]
$[1+1+1+1], $[1+1+1] 1, $[1+1] $[1+1], $[1+1] 1 1,...
Ostrożne stosowanie cudzysłowów, ucieczka przed odwrotnym ukośnikiem i
eval
zapewnienie, że rozszerzenia występują we właściwej kolejności.źródło
Rubin, 61 bajtów
bez golfa
stosowanie
źródło
x<<i
jest krótszy niż[i]+x
..flatten(1)
nie jest.flatten 1
?Brachylog , 20 bajtów
Wypróbuj online!
Wyjaśnienie
Jest to sytuacja, w której można by pomyśleć, że języki deklaratywne byłyby dobre, ale z powodu przeciążenia
+
i trudności w pisaniu predykatu sumującego, który odpowiednio propaguje ograniczenia, nie robią tego.źródło
L
być pomiędzy 1 i wejścia.+
działa również na pojedynczej liczbie całkowitej, muszę wymusić,.
aby być listą##
, a ponieważ+
działa również na liście list, muszę narzucić, że elementami.
są liczby całkowite:#$a
.CJam , 19 bajtów
Wypróbuj online!
Wyjaśnienie
CJam nie ma użytecznego wbudowanego kombinatora dla partycji całkowitych. Zrobimy to ręcznie. Aby znaleźć wszystkie uporządkowane partycje liczb całkowitych
n
, możemy spojrzeć na ich listęn
i rozważyć każdy możliwy sposób wstawienia separatorów. Następnie zsumujemy1
s w każdej sekcji. Przykład dlan = 3
:Próbowałem użyć produktu kartezjańskiego do wygenerowania wszystkich tych separatorów, ale skończyło się to na 21 bajtach. Zamiast tego wróciłem do tej starej techniki generowania zestawów mocy (jest to oparte na starej odpowiedzi Dennisa, ale nie mogę jej teraz znaleźć). Pomysł jest następujący: aby wygenerować wszystkie partycje, możemy zacząć od pustej listy. Potem
n
możemy podjąć decyzję binarną: albo dołączamy a1
(odpowiada separatorowi w powyższym przykładzie), albo zwiększamy ostatnią wartość listy (odpowiada to brakowi separatora). Aby wygenerować wszystkie partycje, po prostu wykonujemy obie operacje na każdym kroku i zachowujemy wszystkie możliwe dane wyjściowe na następny krok. Okazuje się, że w CJam przyspieszenie i zwiększenie pierwszego elementu jest krótsze, ale zasada pozostaje taka sama:źródło
T-SQL, 203 bajty
Gra w golfa:
Nie golfowany:
Skrzypce
źródło
Mathematica 10.0, 44 bajty
Próba bez użycia wbudowanych funkcji partycji. Z każdej uporządkowanej partycji o rozmiarze k generowane są dwie kolejne partycje k + 1 : jedna przez dodanie 1, a druga przez zwiększenie pierwszej wartości.
Zabawniejszy, ale niestety o 2 bajty dłuższy sposób realizacji tego samego pomysłu:
źródło
MapAt
indeks na -1.05AB1E ,
1412 bajtówZaoszczędzono 2 bajty dzięki Adnan
Wyjaśnienie
Wypróbuj online!
Odpowiednie rozwiązanie jest o 2 bajty krótsze w 2sable .
2sable , 10 bajtów
Wypróbuj online!
źródło
—
zamiastiy,
:).Haskell, 41 bajtów
Nie najkrótsze rozwiązanie Haskell, ale podoba mi się, że nie używa
[..]
zakresów. Zamiast tego rekurencyjnie oblicza partycjen
jako partycjen-1
z nową 1 na początku lub pierwszą wartością o jedną wyższą. To wyjaśnia, dlaczego istnieje2^(n-1)
.źródło
Mathematica, 53 bajty
Nie bije odpowiedzi Martina Endera, która korzysta z wbudowanego
IntegerPartitions
funkcji (a wbudowane są dla mnie całkowicie w porządku). (Nie jest to także odpowiedź na feersum, którego nie widziałem aż do późna.) Chciałem jednak ćwiczyć funkcję rekurencyjną w golfa.Rekurencyjnie generuje wszystkie kompozycje, generując wszystkie możliwe liczby końcowe,
j
a następnie wywołując,#-j
gdzie#
jest dane wejściowe.źródło
Array
zamiastTable
i unikającegoAppend
, używając listy iApply
:±0={{}};±n_:=Join@@Array[{##,n-+##}&@@@±#&,n,0]
@@
zrobić?f@@g[a,b]
ocenia naf[a,b]
. Wykorzystujemy tutaj fakt, że lista taka jak{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }
niewidzialna ma głowęList
; więcJoin@@{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }
ocenia doJoin@@List[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]
oceny doJoin[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]
oceny{ {1,1,1}, {2,1}, {1,2}, {3} }
.Siatkówka , 32 bajty
Liczba bajtów zakłada kodowanie ISO 8859-1.
Wypróbuj online!
Wyjaśnienie
Działa to podobnie do mojej odpowiedzi CJam . Przeglądamy listę
N
i na każdej pozycji podejmujemy obie gałęzie decyzji binarnej a) zwiększamy ostatnią wartość lub b) rozpoczynamy nową wartość od 1.Scena 1
Przekształć dane wejściowe w jednoargumentowe.
Etap 2
+
Mówi Retina aby wykonać ten etap w pętli aż wyjście przestaje się zmieniać.%
Mówi to, aby podzielić wejście do linii przed nałożeniem na scenę i połączyć je z powrotem razem później. Umieszczając%
po+
, Retina dzieli się i ponownie dołącza po każdej iteracji. Jedna iteracja etapu podejmuje jedną z tych decyzji, o których wspomniałem, i tym samym rozwidla obecny zestaw partycji.To, jak to naprawdę działa, polega na tym, że pasuje do
1
(ale tylko pierwszego, jak wskazano1
przed tyłem) i zamienia go na!
(który użyjemy jako jednoznacznej cyfry naszego wyjścia), a następnie pozostałe1
s w tym wierszu (zwiększa ostatnią wartość). Następnie w innym wierszu (¶
) wypisuje przedrostek bieżącej linii, a następnie,!
wstawia separator, a następnie rozpoczyna następną wartość od1
.Etap 3
Konwertuje to liczby
!
całkowite na dziesiętne, zastępując je ich długością.Etap 4
I w końcu zauważamy, że wygenerowaliśmy dwa razy więcej wierszy, niż chcieliśmy, a połowa z nich zaczyna się od
,
(tych, w których początkowo podjęliśmy decyzję o podziale, chociaż nie było już nic do podzielenia). Dlatego odrzucamy wszystkie linie zaczynające się od,
.źródło
Perl, 44 bajty
Zawiera +3 za
-n
(używa kodu$'
i$0
dlatego nie mogą być uruchamiane jako-e
poleceń)Podaj numer do partycji na STDIN:
partitions.pl
Jeśli nie przeszkadza ci dodatkowe spacje na końcu wiersza i dodatkowa nowa linia, to 42 bajtowe rozwiązanie również działa (działa jako
perl -M5.010 partitions.pl
):źródło
Julia, 113 bajtów
Rozwiązanie nierekurencyjne
Wyjaśnił:
[vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N]
zbuduj zestaw list, które sumują się do N, których permutacje będą przypominały rozwiązanie (np. dla N = 4: [[1,1,1,1], [1,1,2], [1,3], [4 ]])map(x->[permutations(x)...],)
Oblicz wszystkie permutacjereduce(vcat,)
połącz je w listę listunique()
filtruj duplikatyźródło
N
jako dane wejściowe. Możesz zrobić funkcję lambda, przygotowującN->
ją kosztem 3 bajtów.f(N)=
zgubiłem się podczas kopiowania, miałem to podczas liczenia bajtówMATL , 15 bajtów
Wypróbuj online!
Wyjaśnienie
Biorąc pod uwagę dane wejściowe
n
, oblicza to moc kartezjańską z rosnącymi wykładnikamik
od1
don
; i dla każdego wykładnikak
wybiera krotki o sumie równej wejściowej.źródło
Lua
214203182 bajtówWersja nierozdzielona.
Znaleziono zbłąkane białe znaki i usunęliśmy niepotrzebną zmienną do bezpiecznych 11 bajtów. jak się okazuje, table.insert () jest bajtem nieefektywnym
źródło
PHP, 125 bajtów
-4 bajtów
print_r($r);
zamiastecho json_encode($r);
na wyjścierozwiązanie rekurencyjne z 250 bajtami
źródło
Prolog, 81 bajtów + 6 bajtów do wywołania
Wypróbuj online!
Zadzwoń za pomocą
[4]*L.
, powtórz za pomocą;
aż wszystkie rozwiązania zostaną przedstawione.Alternatywnie, jeśli wielokrotne naciskanie
;
nie jest w porządku (lub powinno zostać dodane do liczby bajtów), połączenie, zbagof(L,[4]*L,M).
którym dodaje 17 bajtów dla połączenia.źródło
J ,
3026 bajtówDziała poprzez podzielenie listy jednych n przy użyciu wartości binarnych 2 n .
Wypróbuj online!
Wyjaśnienie
źródło
Właściwie
1716 bajtówTa odpowiedź jest częściowo oparta na odpowiedzi MATL Luisa Mendo . Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!
Ungolfing
źródło
Właściwie
171615 bajtówJest to interesujący widelec odpowiedzi Martina Endera na CJam (ten z kartezjańskim produktem), z tą różnicą we wdrożeniu, która moim zdaniem była interesująca. Gdy jeden z ciągów Martina zaczyna się od przyrostu, błędy uniemożliwiają ocenę tego ciągu. W rzeczywistości błąd jest pomijany, a łańcuch jest mimo to oceniany. Ostatecznie daje to kompozycje każdego
k
w zakresie[1..n]
.Zamiast próbować usunąć dodatkowe kompozycje, wziąłem
n-1
th kartezjańską moc"1u"
dołączonego"1"
na początku każdego ciągu. Ta sztuczka daje tylko kompozycjen
. Jest niestety dłuższy niż odpowiedź Martina.Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!
Ungolfing
źródło