Listen Sie alle geordneten Partitionen von n auf

23

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]))):[[]]
driima
quelle
3
Willkommen auf der Seite! Sie müssen ein Gewinnkriterium angeben. Code-Golf vielleicht? Muss es auch in dieser bestimmten Reihenfolge sein? Wenn ja, wie ist die Reihenfolge im Allgemeinen definiert? Ich denke, lexikografische Reihenfolge wäre sinnvoller; oder noch besser, erlauben Sie jede Bestellung. Sie können die Sandbox für zukünftige Herausforderungen verwenden, bevor Sie sie hier veröffentlichen
Luis Mendo
3
@Fatalize Hier [2 1 1] ist anders als dort [1 2 1]. Ich vermute, die Ansätze können erheblich anders sein
Luis Mendo
3
Für diejenigen, die als Betrüger geschlossen haben: Sind Sie sicher, dass der in den Kommentaren angegebene Unterschied nicht relevant ist? Ich stimme nicht für die Wiedereröffnung, da ich denke, der Hammer würde auch in diese Richtung wirken
Luis Mendo
3
Ich würde vorschlagen, eine Antwort noch nicht zu akzeptieren (auch wenn Sie sie jederzeit ändern können), da die Frage auf der Titelseite akzeptiert wird und die Leute denken, dass sie vorbei ist und nicht teilnehmen.
Xnor
5
Der übliche Begriff für diese geordneten Partitionen ist " Kompositionen ".
Greg Martin

Antworten:

7

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
Steven H.
quelle
Tolle. Dies ist die kleinste, die ich bisher gesehen habe!
Driima
11

Haskell, 37 Bytes

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

xnor sparte zwei Bytes.

Lynn
quelle
1
Es sieht so aus, als ob das Geradlinigere f n=[a:x|a<-[1..n],x<-f$n-a]kürzer ist.
Xnor
Sie brauchen nicht die given positive integer n ... numbers from 1 to n
Nullprüfung
2
f 0=[[]]Zufällig ist es ein kürzerer Basisfall als f 1=[[1]]:)
Lynn
@xyLe_ Es wird ein rekursiver Basisfall verwendet.
22.
ach
ja
10

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.

xnor
quelle
Einfach, klein und doch erstaunlich lesbar. Das ist es, was ich an Python liebe.
Driima
10

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.

xnor
quelle
Bester nicht-rekursive Version , die ich tun konnte , warimport re lambda n:map(lambda n:map(len,re.finall('10*',bin(n))),range(1<<n-1,1<<n))
Neil
1
Eine Erklärung mit dem Code würde es wirklich schön machen.
Noman Pouigt
8

JavaScript (Firefox 30-57), 63 Byte

f=n=>n?[for(i of Array(n).keys())for(a of f(i))[n-i,...a]]:[[]]
Neil
quelle
12
Firefox 30+ klingt wie ein spezieller Browser für erfahrene Internetnutzer.
Martin Ender
Wird
Wie kann dies für JavaScript in anderen Browsern deaktiviert werden?
Driima
@Eternity Ich kann port @ xnor die andere Antwort für Sie: f=n=>n<2?[[1]]:f(n-1).map(([n,...a])=>r.push([1+n,...a],[1,n,...a]),r=[])&&r.
Neil
6

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.

Martin Ender
quelle
6

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.
}/
Martin Ender
quelle
Ich habe mir das angeschaut und dachte " Das kann nicht richtig sein, es würde einen Fehler geben, wenn es den ersten String auswertet, der mit) " beginnt . Also habe ich hinzugefügt edund getestet. +1 für kreativen Missbrauch von Fehlern.
Peter Taylor
6

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]]
Jonathan Allan
quelle
5

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.

Digitales Trauma
quelle
4

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]]
cia_rana
quelle
2
Hiya! Könntest du ein paar Erklärungen für Leute (wie ich) hinzufügen, die nicht mit Ruby vertraut sind?
AdmBorkBork
x<<iist kürzer als [i]+x.
m-chrzan
@TimmyD Ich habe einen ungolfed Code und die Verwendung hinzugefügt.
cia_rana
@ m-chrzan Danke für deinen Rat! Das habe ich bearbeitet.
Cia_rana
Irgendein Grund .flatten(1)ist nicht .flatten 1?
Cyoce
3

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
Tödlich
quelle
Ich denke , dass dies eine Menge propagieren würde schneller , wenn Sie auf das konzentrieren , positive ganze Zahlen sind , und lassen Sie von der Länge Lsein zwischen 1 und Eingang.
Mat
@mat Das habe ich ursprünglich gemacht, aber das ist länger . Da +auch eine einzelne Ganzzahl bearbeitet wird, muss erzwungen .werden, eine Liste mit zu sein ##, und da +auch eine Liste mit Listen bearbeitet wird, muss erzwungen werden, dass die Elemente von .Ganzzahlen mit sind :#$a.
Fatalize
Das Hauptproblem ist also die Standardmäßigkeit der Datenstrukturen: Wenn eine Variable als Argumente für vektorisierende Operationen angezeigt wird, können Sie nicht erkennen, ob die Variable für eine einzelne Ganzzahl oder eine (möglicherweise verschachtelte) Liste steht. Dies ist ein schwieriges Problem, und es gibt möglicherweise eine elegante Möglichkeit, dieses Problem zu lösen. Beginnen Sie mit Ihrer Originalversion und suchen Sie nach geeigneten Sprachkonstrukten, die dies vereinfachen könnten. Gute Arbeit auf jeden Fall!
Mat
3

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.
Martin Ender
quelle
3

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

t-clausen.dk
quelle
3

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]&
Feersum
quelle
@alephalpha Nein, das würde nicht helfen, da ich dann den MapAtIndex auf -1 ändern müsste .
Feersum
3

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!

Emigna
quelle
Sie können anstelle von iy,:) verwenden.
Adnan
@Adnan: Danke! Das habe ich vergessen.
Emigna
3

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.

xnor
quelle
3

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.

Greg Martin
quelle
Sie können einige Bytes einsparen, indem Sie Arrayanstelle von einen Operator definieren Tableund dies vermeiden, Appendindem Sie eine Liste verwenden und Apply:±0={{}};±n_:=Join@@Array[{##,n-+##}&@@@±#&,n,0]
Martin Ender,
Was macht @@das?
Cyoce
Es ersetzt den "Kopf" eines Ausdrucks. Wertet zum Beispiel f@@g[a,b]zu aus f[a,b]. Hier verwenden wir die Tatsache, dass eine Liste wie { { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }unsichtbar Kopf hat List; so Join@@{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }wertet aus, Join@@List[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]um zu Join[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]bewerten, um zu bewerten { {1,1,1}, {2,1}, {1,2}, {3} }.
Greg Martin
3

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

Martin Ender
quelle
3

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
Tonne Hospel
quelle
3

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
nyro_0
quelle
Wir fordern, dass die Einsendungen vollständige Programme oder Funktionen sind. In diesem Fall müssen Sie also NEingaben vornehmen. Sie können eine Lambda-Funktion erstellen, indem Sie N->3 Byte voranstellen .
Alex A.
@AlexA. Oh, tut mir leid f(N)=, dass ich mich beim Kopieren verlaufen habe. Ich hatte es beim Zählen von Bytes
nyro_0
2

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
Luis Mendo
quelle
1

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

lenscas
quelle
1

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));
Jörg Hülsermann
quelle
1

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 .

SQB
quelle
1

J , 30 26 Bytes

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

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

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
Meilen
quelle
0

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.
Sherlock9
quelle
0

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.
Sherlock9
quelle