Wyzwanie polega na wyświetleniu listy wszystkich uporządkowanych partycji (kompozycji (kombinatoryki)) danej dodatniej liczby całkowitej n. Są wykazy numerów od 1do nktórych suma jest n. Na przykład przy danych wejściowych n = 4wynik 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]))):[[]]

Pyth, 7 6 bajtów

7 bajtowe rozwiązanie:

Pyth ma wbudowaną partycję całkowitą ./ , więc 5 z 7 bajtów otrzymuje porządek.

{s.pM./

Wypróbuj online!

Wyjaśnienie:

     ./  Integer partition (sorted by default)
  .pM    get all the orderings of each of the partitions as a nested list of lists of orderings
 s       Flatten by one layer
{        Remove duplicates

6 bajtowe rozwiązanie:

Jeśli masz listę, ./będzie obliczać z zamówieniami; wszystko, co pozostaje, to ponowne utworzenie numerów list.

lMM./m

Wypróbuj online!

Wyjaśnienie:

     m  Get lists by gathering a list of [0, 1,...input] (I could use U as well)

   ./   Partition with orderings
 MM     Map an operation across each of the orderings lists of elements
l       where that operation is the length of the sublists

Haskell, 37 bajtów

f 0=[[]]
f n=[a:x|a<-[1..n],x<-f$n-a]

xnor zapisał dwa bajty.

Python, 56 bajtów

f=lambda n:[x+[n-i]for i in range(n)for x in f(i)]or[[]]

Cykliczna rozwiązanie: zamawiane partycje nsą podział niektóre mniejsze iz 0<=i<n, a następnie pozostałą n-ijako ostatniego elementu. W przypadku podstawowym n=0ma tylko pustą partycję.

Python 2, 61 bajtów

f=lambda n,s='1,':1/n*[eval(s)]or f(n-1,'1+'+s)+f(n-1,'1,'+s)

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 jak

1+1+1+1,
1,1+1+1,
1+1,1+1,
1,1,1+1,
1+1+1,1,
1,1+1,1,
1+1,1,1,
1,1,1,1,

dla 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.

JavaScript (Firefox 30-57), 63 bajty

f=n=>n?[for(i of Array(n).keys())for(a of f(i))[n-i,...a]]:[[]]

Mathematica, 40 bajtów

Join@@Permutations/@IntegerPartitions@#&

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.

CJam , 17 14 bajtów

ri"X)"m*{~]p}/

Wypró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ć nczasy między dołączeniem a 1do 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.

ri      e# Read input and convert to integer N.
        e# Decrement.
"X)"m*  e# Get all strings of length N which consist of 'X' and ')'. If
        e# we treat these strings as CJam code then 'X' pushes a 1 and ')'
        e# increments the top of the stack.
        e# Note that some of these strings will begin with an increment that
        e# doesn't have anything on the stack to work with. This will result in
        e# an error and terminate the program. Luckily, the programs are ordered
        e# such that all programs starting with 'X' are first in the list, so
        e# we get to print all the 2^(N-1) permutations before erroring out.
{       e# For each of these programs (well for the first half of them)...
  ~     e#   Evaluate the string as CJam code. This leaves the partition as
        e#   individual integers on the stack.
  ]p    e#   Wrap the stack in a list and pretty-print it.
}/

Galaretka , 7 6 bajtów

-1 bajt dzięki @Dennis (konwertuj z unary ḅ1, zamiast sumy dla każdego dla każdego S€€)

1ẋŒṖḅ1

TryItOnline

W jaki sposób?

1ẋŒṖḅ1 - Main link: n          e.g. 4
1ẋ     - repeat 1 n times          [1,1,1,1]
  ŒṖ   - partitions of a list     [[[1],[1],[1],[1]], [[1],[1],[1,1]], [[1],[1,1],[1]],
                                   [[1],[1,1,1]],     [[1,1],[1],[1]], [[1,1],[1,1]],
                                   [[1,1,1],[1]],     [[1,1,1,1]]]
    ḅ1 - from base 1 (vectorises)  [[1,1,1,1],        [1,1,2],         [1,2,1],
                                   [1,3],             [2,1,1],         [2,2],
                                   [3,1],             [4]]

Pure Bash, 51

To jest część doskonałej odpowiedzi @ xnor , wykorzystującej wiele poziomów rozszerzeń bash, aby osiągnąć pożądany rezultat:

a=$[10**($1-1)]
eval echo \$[${a//0/{+,']\ $[}1'}],

Ideone.

• Pierwszy wiersz jest po prostu rozszerzeniem arytmetycznym w celu utworzenia zmiennej $azawierającej 1następujące po nim n-1zera.
• Pierwsze rozszerzenie ${a//0/{+,']\ $[}1'}zamienia każde 0na $akopie ciągu {+,']\ $[}1'. Zatem n = 4 otrzymujemy ciąg1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1'
• Jest to poprzedzone $[i po tym, ],aby dać$[1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1]
• To rozszerzenie nawiasu klamrowego, które się rozwija $[1+1+1+1], $[1+1+1] 1, $[1+1] $[1+1], $[1+1] 1 1,...
• Jest to wreszcie rozszerzane arytmetycznie, aby dać wymagany wynik.

Ostrożne stosowanie cudzysłowów, ucieczka przed odwrotnym ukośnikiem i evalzapewnienie, że rozszerzenia występują we właściwej kolejności.

Rubin, 61 bajtów

f=->n{n<1?[[]]:(1..n).map{|i|f[n-i].map{|x|x<<i}}.flatten(1)}

bez golfa

f=->n{
  n < 1 ?
    [[]]
  :
    (1..n).map { |i|
      f[n-i].map { |x|
        x << i
      }
    }.flatten(1)
}

stosowanie

p f[4]
# => [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]

Brachylog , 20 bajtów

~lL#++?,L:=f:{:0x}ad

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.

~lL                     L is a list of length Input
  L#+                   L is a list of non-negative integers
  L  +?,                The sum of the elements of L results in the Input
        L:=f            Find all values for the elements of L which satisfy those constraints
            :{:0x}a     Remove all 0s from each sublist of the result of Findall
                   d    Remove all duplicate sublists

CJam , 19 bajtów

Lari{_1af.+1@f+|}*p

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ę ni rozważyć każdy możliwy sposób wstawienia separatorów. Następnie zsumujemy 1s w każdej sekcji. Przykład dla n = 3:

1 1 1 => 3
1 1|1 => 2|1
1|1 1 => 1|2
1|1|1 => 1|1|1

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 nmożemy podjąć decyzję binarną: albo dołączamy a 1(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:

La       e# Push [[]] onto the stack. The outer list will be the list of
         e# all possible partitions at the current iteration, and we initialise
         e# it to one empty partition (basically all partitions of 0).
ri       e# Read input and convert to integer N.
{        e# Repeat this N times...
  _      e#   Duplicate the list of partitions of i-1.
  1af.+  e#   Increment the first element in each of these. This is done
         e#   by performing a pairwise addition between the partition and [1].
         e#   There is the catch that in the first iteration this will turn
         e#   the empty array into [1], so it's equivalent to the next step.
  1@f+   e#   Pull up the other copy of the list of partitions of i-1 and
         e#   prepend a 1 to each of them.
  |      e#   Set union. This gets rid of the duplicate result from the first
         e#   iteration (in all other iterations this is equivalent to concatenating
         e#   the two lists).
         e#   Voilà, a list of all partitions of i.
}*
p        e# Pretty-print the result.

T-SQL, 203 bajty

Gra w golfa:

USE master
DECLARE @ INT=12

;WITH z as( SELECT top(@)cast(number+1as varchar(max))a FROM spt_values WHERE'P'=type),c as(SELECT a*1a,a b FROM z UNION ALL SELECT c.a+z.a,b+','+z.a FROM c,z WHERE c.a+z.a*1<=@)SELECT b FROM c WHERE a=@

Nie golfowany:

USE master --needed to make sure it is executed from the correct database
DECLARE @ INT=12

;WITH z as
(
  SELECT top(@)cast(number+1as varchar(max))a
  FROM spt_values
  WHERE'P'=type
),c as
(
  SELECT a*1a,a b
  FROM z
  UNION ALL
  SELECT c.a+z.a,b+','+z.a
  FROM c,z
  WHERE c.a+z.a*1<=@
)
SELECT b 
FROM c
WHERE a=@

Skrzypce

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.

Nest[##&[{1,##},{#+1,##2}]&@@@#&,{{1}},#-1]&

Zabawniejszy, ale niestety o 2 bajty dłuższy sposób realizacji tego samego pomysłu:

#@{1}&/@Tuples[Prepend[1]@*MapAt[#+1&,1],#-1]&

05AB1E , 14 12 bajtów

Zaoszczędzono 2 bajty dzięki Adnan

>G¹LNãvyO¹Q—

Wyjaśnienie

>G              # for N in range(1..input)
  ¹L            # range(1, input)
    Nã          # cartesian product with N (all combinations of length N)
      v         # for each resulting list
       yO¹Q—    # if it's sum equals the input print it

Wypróbuj online!

Odpowiednie rozwiązanie jest o 2 bajty krótsze w 2sable .

2sable , 10 bajtów

>GLNãvyOQ—

Wypróbuj online!

Haskell, 41 bajtów

f 1=[[1]]
f n=do a:b<-f$n-1;[1:a:b,a+1:b]

Nie najkrótsze rozwiązanie Haskell, ale podoba mi się, że nie używa [..]zakresów. Zamiast tego rekurencyjnie oblicza partycjen jako partycje n-1z nową 1 na początku lub pierwszą wartością o jedną wyższą. To wyjaśnia, dlaczego istnieje 2^(n-1).

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.

If[#<1,{{}},Join@@Table[#~Append~j&/@#0[#-j],{j,#}]]&

Rekurencyjnie generuje wszystkie kompozycje, generując wszystkie możliwe liczby końcowe, ja następnie wywołując, #-jgdzie #jest dane wejściowe.

Siatkówka , 32 bajty

Liczba bajtów zakłada kodowanie ISO 8859-1.

.+
$*
+%1`1
!$'¶$`,!
!+
$.&
A`^,

Wypróbuj online!

Wyjaśnienie

Działa to podobnie do mojej odpowiedzi CJam . Przeglądamy listę Ni 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

+%1`1
!$'¶$`,!

+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 wskazano 1przed tyłem) i zamienia go na !(który użyjemy jako jednoznacznej cyfry naszego wyjścia), a następnie pozostałe 1s 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ść od 1.

Etap 3

!+
$.&

Konwertuje to liczby !całkowite na dziesiętne, zastępując je ich długością.

Etap 4

A`^,

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 ,.

Perl, 44 bajty

Zawiera +3 za -n(używa kodu $'i $0dlatego nie mogą być uruchamiane jako -epoleceń)

Podaj numer do partycji na STDIN:

partitions.pl <<< 4

partitions.pl

#!/usr/bin/perl -n
$_=$&-$_.",$_$'",do$0for/\d+/..$&-1;print

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

#!/usr/bin/perl -n
$_=$`-$_." $_ $'",do$0for/\s/..$_-1;say

Julia, 113 bajtów

f(N)=unique(reduce(vcat,(map(x->[permutations(x)...],[vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N]))))

Rozwiązanie nierekurencyjne

Wyjaśnił:

1. [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 ]])
2. map(x->[permutations(x)...],) Oblicz wszystkie permutacje
3. reduce(vcat,) połącz je w listę list
4. unique() filtruj duplikaty

MATL , 15 bajtów

:"G:@Z^t!XsG=Y)

Wypróbuj online!

Wyjaśnienie

Biorąc pod uwagę dane wejściowe n, oblicza to moc kartezjańską z rosnącymi wykładnikami kod 1do n; i dla każdego wykładnika kwybiera krotki o sumie równej wejściowej.

:       % Take input n implicitly and push range [1 2 ... n]
"       % For each k in that range
  G:    %   Push [1 2 ... n] again
  @     %   Push k
  Z^    %   Cartesian power. Gives 2D array, say A, with each k-tuple in a row.
  t     %   Duplicate
  !     %   Transpose
  Xs    %   Sum of each column. Gives a row vector
  G=    %   True for entries that equal the input
  Y)    %   Use as logical vector into the rows of array A
        % End implicitly
        % Display stack implicitly

Lua 214 203 182 bajtów

function g(m, l, n,c)for i=1,m do if i+n < m then l[#l+1]=i;g(m,l,n+i,c+1)elseif i+n == m then l[#l+1]=i;print(unpack(l))end end for k=c,#l do l[k]=nil end end g(io.read()*1,{},0,0)

Wersja nierozdzielona.

function g(m, l, n,c)
    for i=1,m do 
        if i+n < m then 
            l[#l+1]=i
            g(m,l,n+i,c+1)
        elseif i+n == m then 
            l[#l+1]=i
            print(unpack(l))
        end 
    end 
    for k=c,#l do 
        l[k]=nil 
    end 
end 
g(io.read()*1,{},0,0)

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

PHP, 125 bajtów

for($i=$n=$argv[1];$i<=str_repeat(1,$n);$i++)if(array_sum($a=str_split($i))==$n&!strpos($i,"0"))$r[]=$a;echo json_encode($r);

-4 bajtów print_r($r);zamiastecho json_encode($r); na wyjście

rozwiązanie rekurencyjne z 250 bajtami

function f($n){global$a;foreach($a as$x)foreach(range(1,$n)as$y)$a[]=array_merge((array)$x,[$y]);if(--$n)f($n);}$a=range(1,$w=$argv[1]);f($w-1);foreach($a as$z)if(array_sum((array)$z)==$w)$c[join("-",(array)$z)]=$z;echo json_encode(array_values($c));

Prolog, 81 bajtów + 6 bajtów do wywołania

L*L.
[H|T]*L:-H>1,M is H-1,[M,1|T]*L.
[H,K|T]*L:-H>1,M is H-1,N is K+1,[M,N|T]*L.

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, z bagof(L,[4]*L,M).którym dodaje 17 bajtów dla połączenia.

J , 30 26 bajtów

#&1<@(+/;.1)~2#:@(+i.)@^<:

Działa poprzez podzielenie listy jednych n przy użyciu wartości binarnych 2 ⁿ .

Wypróbuj online!

Wyjaśnienie

#&1<@(+/;.1)~2#:@(+i.)@^<:  Input: n
                        <:  Decrement n
             2         ^    Compute 2^(n-1)
                 (   )@     Operate on that
                   i.         Make the range [0, 1, ..., 2^(n-1)-1]
                  +           Add 2^(n-1) to each in that range
              #:@           Convert each in that range to binary
#&1                         Make n copies of 1 (n in unary)
     (     )~               Operate over each row on RHS and unary n on LHS
        ;.1                   Chop unary n starting at each 1
      +/                        Reduce by addition on each chop
   <@                           Box the sums of each chop

Właściwie 17 16 bajtów

Ta odpowiedź jest częściowo oparta na odpowiedzi MATL Luisa Mendo . Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

;╗R`╜R∙i`M`Σ╜=`░

Ungolfing

         Implicit input n.
;╗       Duplicate n and save a copy of n to register 0.
R        Take the range of [1..n].
`...`M   Map the following function over the range. Variable k.
  ╛R       Push n from register 0 and take the range [1..n] again.
  ∙        Take the k-th Cartesian power of the range.
  i        Flatten that product.
`...`░   Push values of the previous map where the following function returns a truthy value.
          Variable L.
  Σ        Push sum(L).
  ╜        Push n from register 0.
  =        Check if sum(L) == n.
         Implicit return.

Właściwie 17 16 15 bajtów

Jest 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 kw zakresie [1..n].

Zamiast próbować usunąć dodatkowe kompozycje, wziąłem n-1th 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!

D"1u"∙`1@Σ£ƒk`M

Ungolfing

         Implicit input n.
D        Decrement n.
"1u"∙    Take the (n-1)th Cartesian power of the string "1u".
          In Actually, 1 pushes 1 to the stack and u is increment.
`...`M   Map the following function over the Cartesian power. Variable s.
  1@       Push a 1 to be used later.
  Σ        Summing a list of chars joins the chars into one string.
  £ƒ       Turn s into a function and call it immediately on the 1 in the stack.
  k        Take the whole stack and wrap in a list. This is a composition of n.
         Implicit return.