Die Herausforderung besteht darin, alle geordneten Partitionen (Zusammensetzung (Kombinatorik)) einer bestimmten positiven ganzen Zahl aufzulisten n. Dies sind die Nummernlisten von 1bis zu nderen Summe n. Zum Beispiel n = 4sollte das Ergebnis bei einer gegebenen Eingabe sein:

4
1, 3
3, 1
2, 2
2, 1, 1
1, 2, 1
1, 1, 2
1, 1, 1, 1

Das Ergebnis kann in beliebiger Reihenfolge vorliegen, muss jedoch jede geordnete Partition einmal enthalten. Dies bedeutet , dass für n = 4, [1, 1, 2], [1, 2, 1]und [2, 1, 1]muß alle Teile des Ergebnisses sein.

Hier ist mein eigener JavaScript-Code, der dies erreicht:

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

Golf, ES6 ( 169 167 119 109 105 89 85 Byte ):

n=>n?[].concat(...[...Array(n)].map((x,i)=>i+1).map(b=>m(n-b).map(a=>[b,...a]))):[[]]

Pyth, 7 6 Bytes

7 Byte Lösung:

In Pyth ist eine Ganzzahlpartition integriert ./, sodass 5 der 7 Bytes die Reihenfolge erhalten.

{s.pM./

Probieren Sie es online!

Erläuterung:

     ./  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 Byte Lösung:

Wenn Sie eine Liste haben, ./wird mit Bestellungen berechnet; Alles was bleibt ist, die Listen erneut zu nummerieren.

lMM./m

Probieren Sie es online!

Erläuterung:

     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 Bytes

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

xnor sparte zwei Bytes.

Python, 56 Bytes

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

Eine rekursive Lösung: Die geordneten Teilungen nsind eine Partition von einigen kleineren imit 0<=i<n, durch den Rest gefolgt n-ials letztes Element. In einem Basisfall ist n=0nur die Partition leer.

Python 2, 61 Bytes

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

Dies ist nicht die kürzeste, aber ich mag die Methode wirklich, weil sie so seltsam ist.

Generiert rekursiv und wertet 2**(n-1)Strings wie

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,

für n=4. Diese Zeichenfolgen werden zu Tupeln ausgewertet, die alle Partitionen darstellen. Zwischen zwei Einsen befindet sich entweder eine +, die sie zu einer einzigen Zahl zusammenfügt, oder eine ,, die benachbarte Abschnitte aufteilt.

JavaScript (Firefox 30-57), 63 Byte

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

Mathematica, 40 Bytes

Join@@Permutations/@IntegerPartitions@#&

Die in Mathematica integrierte Funktion für ganzzahlige Partitionen gibt nicht alle geordneten Partitionen an. Wir müssen daher alle möglichen Permutationen für jede dieser Partitionen generieren und dann das Ergebnis reduzieren.

CJam , 17 14 Bytes

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

Probieren Sie es online!

Erläuterung

Ich wusste, dass die Verwendung des kartesischen Produkts länger dauert, fand aber schließlich einen Weg, es effizienter zu nutzen. Ich denke, dass beide Ansätze für sich genommen interessant sind, also setze ich sie in separate Posts.

Dies basiert immer noch auf der Idee, dass wir nzwischen dem Anhängen eines 1an die aktuelle Partition oder dem Inkrementieren des letzten Elements der aktuellen Partition wählen können . In dieser Lösung erzeugen wir dazu 2 ^n-1 verschiedene Programme, die diesen verschiedenen Auswahlen entsprechen.

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.
}/

Gelee , 7 6 Bytes

-1 Byte dank @Dennis (von unary konvertieren ḅ1, anstatt Summe für jeden für jeden S€€)

1ẋŒṖḅ1

TryItOnline

Wie?

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

Dies ist eine Portierung von @ xnors brillanter Antwort , die mehrere Stufen von Bash-Erweiterungen verwendet, um das gewünschte Ergebnis zu erzielen:

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

Ideone.

• Die erste Zeile ist einfach eine arithmetische Erweiterung, um eine Variable zu erstellen, $adie 1gefolgt von n-1Nullen ist.
• Die erste Erweiterung ${a//0/{+,']\ $[}1'}ersetzt jeden 0in $aKopien der Zeichenfolge {+,']\ $[}1'. Also n = 4 bekommen wir den String1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1'
• Dies wird mit vorangestellt $[und mit nachfixiert ],zu geben$[1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1]
• Dies ist eine Klammererweiterung, auf die erweitert wird $[1+1+1+1], $[1+1+1] 1, $[1+1] $[1+1], $[1+1] 1 1,...
• Dies wird schließlich arithmetisch erweitert, um das gewünschte Ergebnis zu erhalten.

Sorgfältiger Umgang mit Anführungszeichen, Backslash und evalSicherstellung, dass die Erweiterungen in der richtigen Reihenfolge erfolgen.

Ruby, 61 Bytes

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

ungolfed

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

Verwendung

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 Bytes

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

Probieren Sie es online!

Erläuterung

Dies ist eine Situation, in der man denken würde, dass deklarative Sprachen gut funktionieren würden, aber aufgrund der Überlastung +und der schwierigen Schreibweise eines Summierungsprädikats, das Einschränkungen richtig propagiert, tun sie dies nicht.

~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 Bytes

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

Probieren Sie es online!

Erläuterung

In CJam ist keine nützliche Kombinatorik für ganzzahlige Partitionen integriert. Also machen wir das manuell. Um alle geordneten Partitionen einer Ganzzahl zu finden n, können wir uns eine Liste von Partitionen ansehen nund überlegen, wie Trennzeichen eingefügt werden können. Dann werden wir die 1s in jedem Abschnitt summieren . Beispiel für n = 3:

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

Ich habe versucht, mit einem kartesischen Produkt alle diese Trennzeichen zu generieren, aber das ergab 21 Byte. Stattdessen bin ich auf diese alte Technik zur Stromerzeugung zurückgegangen (diese basiert auf einer alten Antwort von Dennis, aber ich kann sie derzeit nicht finden). Die Idee ist: Um alle Partitionen zu generieren, können wir von einer leeren Liste ausgehen. Dann nkönnen wir mal eine binäre Entscheidung treffen: Entweder wir hängen ein an 1(entspricht einem Trennzeichen im obigen Beispiel) oder wir erhöhen den letzten Wert der Liste (entspricht dem Fehlen eines Trennzeichens). Um alle Partitionen zu generieren, führen wir einfach beide Operationen bei jedem Schritt durch und behalten alle möglichen Ausgaben für den nächsten Schritt. Es stellt sich heraus, dass in CJam das Voranstellen und Inkrementieren des ersten Elements kürzer ist, das Prinzip jedoch dasselbe bleibt:

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 Bytes

Golf gespielt:

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=@

Ungolfed:

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=@

Geige

Mathematica 10.0, 44 Bytes

Ein Versuch, ohne partitionsbezogene Builtins zu verwenden. Aus jeder geordneten Partition der Größe k werden zwei Nachfolgepartitionen von k + 1 erzeugt: eine durch Voranstellen von 1 und die andere durch Inkrementieren des ersten Werts.

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

Ein lustigerer, aber leider 2 Bytes längerer Weg, die gleiche Idee umzusetzen:

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

05AB1E , 14 12 Bytes

2 Bytes gespart dank Adnan

>G¹LNãvyO¹Q—

Erläuterung

>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

Probieren Sie es online!

Die entsprechende Lösung ist in 2sable 2 Byte kürzer .

2sable , 10 Bytes

>GLNãvyOQ—

Probieren Sie es online!

Haskell, 41 Bytes

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

Nicht die kürzeste Haskell-Lösung, aber ich mag, dass sie keine [..]Bereiche verwendet. Stattdessen werden die Partitionen von rekursiv nals die Partitionen von n-1entweder mit einer neuen 1 am Anfang oder mit dem ersten Wert eins höher berechnet. Dies macht deutlich, warum es 2^(n-1)von ihnen gibt.

Mathematica, 53 Bytes

Die Antwort von Martin Ender, der die eingebaute IntegerPartitionsFunktion verwendet, ist unschlagbar (und die eingebauten Funktionen sind für mich völlig in Ordnung). (Es schlägt auch nicht die Antwort von feersum, die ich erst zu spät gesehen habe.) Aber ich wollte eine rekursive Golffunktion üben.

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

Generiert rekursiv alle Kompositionen, indem alle möglichen endgültigen Zahlen generiert jund sich dann selbst anfragt, #-jwo #die Eingabe ist.

Retina , 32 Bytes

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.

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

Probieren Sie es online!

Erläuterung

Das funktioniert ähnlich wie bei meiner CJam-Antwort . Wir gehen eine Liste durch Nund an jeder Position nehmen wir beide Zweige der binären Entscheidung a) erhöhen den letzten Wert oder b) beginnen einen neuen Wert bei 1.

Bühne 1

.+
$*

Konvertieren Sie die Eingabe in Unary.

Stufe 2

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

Das +weist Retina an, diese Phase in einer Schleife auszuführen, bis sich der Ausgang nicht mehr ändert. Das %weist es an, die Eingabe vor dem Anwenden der Bühne in Zeilen aufzuteilen und diese anschließend wieder zusammenzufügen. Durch das Setzen der %nach dem+ , spaltet sich Retina nach jeder Iteration auf und kehrt wieder zurück. Eine Iteration der Stufe trifft eine dieser Entscheidungen, die ich erwähnt habe, und teilt dadurch die aktuelle Menge von Partitionen auf.

Wie es tatsächlich funktioniert, stimmt es mit einem überein 1(aber nur mit dem ersten, wie durch das 1vor dem Backtick angegeben) und ersetzt es durch !(das wir als unäre Ziffer unserer Ausgabe verwenden), gefolgt von dem verbleibenden 1s in dieser Zeile (dies erhöht den letzten Wert). Dann wird in einer anderen Zeile ( ¶) das Präfix der aktuellen Zeile gedruckt, gefolgt von ,!einem Trennzeichen, und der nächste Wert beginnt bei 1.

Stufe 3

!+
$.&

Dadurch werden die Läufe von !in Dezimalzahlen konvertiert, indem sie durch ihre Länge ersetzt werden.

Stufe 4

A`^,

Und schließlich stellen wir fest, dass wir doppelt so viele Zeilen generiert haben, wie wir wollten, und die Hälfte von ihnen beginnt mit einem ,(die, bei denen wir ursprünglich die Entscheidung getroffen haben, zu teilen, obwohl es danach noch nichts zu teilen gab). Aus diesem Grund verwerfen wir alle Zeilen, die mit einem beginnen ,.

Perl, 44 Bytes

Beinhaltet +3 für -n(Code wird verwendet $'und $0kann daher nicht als -eBefehlszeile ausgeführt werden)

Partition auf STDIN nummerieren:

partitions.pl <<< 4

partitions.pl

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

Wenn Sie keine zusätzlichen Leerzeichen am Ende einer Zeile und einen zusätzlichen Zeilenumbruch beachten, funktioniert diese 42-Byte-Lösung auch (ausgeführt als perl -M5.010 partitions.pl):

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

Julia, 113 Bytes

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

Nicht rekursive Lösung

Erklärt:

1. [vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N] Erstellen Sie eine Reihe von Listen, die sich zu N addieren, deren Permutationen der Lösung ähneln (z. B. für N = 4: [[1,1,1,1], [1,1,2], [1,3], [4 ]])
2. map(x->[permutations(x)...],) Berechnen Sie alle Permutationen
3. reduce(vcat,) Kombiniere sie zu einer Liste von Listen
4. unique() Duplikate filtern

MATL , 15 Bytes

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

Probieren Sie es online!

Erläuterung

Bei gegebener Eingabe nberechnet dies die kartesische Potenz mit zunehmenden Exponenten kvon 1bis n; und kwählt für jeden Exponenten die Tupel aus, deren Summe der Eingabe entspricht.

:       % 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 Bytes

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)

Ungelöste Version.

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)

Es wurde ein verirrtes Leerzeichen gefunden und eine unnötige Variable entfernt, um 11 Byte zu sparen. Wie sich herausstellt, ist table.insert () byte-ineffizient

PHP, 125 Bytes

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 Bytes für print_r($r);statt echo json_encode($r);für die Ausgabe

eine rekursive Lösung mit 250 Bytes

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 Bytes + 6 Bytes zum Aufrufen

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.

Probieren Sie es online!
Rufen Sie mit an [4]*L., wiederholen Sie mit, ;bis alle Lösungen präsentiert wurden.

Alternativ, wenn wiederholtes Drücken ;nicht in Ordnung ist (oder zur Byteanzahl hinzugefügt werden sollte), rufen Sie auf, bagof(L,[4]*L,M).wodurch 17 Bytes für den Anruf hinzugefügt werden .

J , 30 26 Bytes

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

Arbeitet durch Teilen der Liste von unären n unter Verwendung der Binärwerte von 2 ⁿ .

Probieren Sie es online!

Erläuterung

#&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

Eigentlich 17 16 Bytes

Diese Antwort basiert teilweise auf Luis Mendos MATL-Antwort . Golfvorschläge sind willkommen. Probieren Sie es 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.

Eigentlich 17 16 15 Bytes

Dies ist eine interessante Abzweigung von Martin Enders CJam-Antwort (die mit dem kartesischen Produkt), mit einem Unterschied in der Implementierung, den ich interessant fand. Wenn eine von Martins Zeichenfolgen mit einem Inkrement beginnt, verhindern die Fehler, dass diese Zeichenfolge ausgewertet wird. In Actually wird der Fehler unterdrückt und der String trotzdem ausgewertet. Dies führt dazu, dass die Kompositionen von jedem kim Bereich angegeben werden [1..n].

Anstatt zu versuchen, die zusätzlichen Kompositionen zu entfernen, habe ich die n-1kartesische Potenz von "1u"a "1"an den Anfang jeder Saite angehängt . Dieser Trick gibt nur die Kompositionen von n. Es ist leider länger als Martins Antwort.

Golfvorschläge sind willkommen. Probieren Sie es 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.