Generieren Sie alle Unterlistenpartitionen

11

Geben Sie bei einer nicht leeren Liste von Ganzzahlen jede mögliche Partitionierung der Liste aus, wobei jede Partition eine nicht leere Unterliste ist.

Für die Liste [1, 2, 3, 4]lautet das Ergebnis also:

[[1, 2, 3, 4]]
[[1, 2, 3], [4]]
[[1, 2], [3, 4]]
[[1, 2], [3], [4]]
[[1], [2, 3, 4]]
[[1], [2, 3], [4]]
[[1], [2], [3, 4]]
[[1], [2], [3], [4]]

Die Reihenfolge der Listen in der Ausgabe spielt keine Rolle, kann [[1, 2, 3, 4]]also zuerst, zuletzt oder wo auch immer sein. Die Reihenfolge der Elemente muss beibehalten werden.

Dies ist Code-Golf, also gewinnt die kürzeste Antwort.


Verwandte: Partitionieren Sie eine Liste!

mbomb007
quelle
2
Können wir die Umgebung [...]im Ausgabeformat weglassen ? (Solange Partitionen klar voneinander getrennt sind, z. B. durch Zeilenvorschübe.)
Martin Ender
Eingabe- und Ausgabeformate sind flexibel, sollten jedoch ähnlich sein. Wenn die Eingabeliste ihre Elemente in einer Zeile enthält, sollten dies auch die Ausgabelisten tun.
mbomb007
Das ist nicht das was ich meine. Schauen Sie sich die Antwort von Bash an. Es wird :als Listentrennzeichen verwendet, aber in der Ausgabe werden Partitionen selbst nicht in ein zusätzliches Paar von eingeschlossen [...].
Martin Ender
Oder anders gefragt: Kann ich in Ihrem Beispielformat in der Herausforderung die erste [und die letzte ]Zeile aus jeder Zeile entfernen?
Martin Ender

Antworten:

13

Netzhaut , 27 19 Bytes

Die Byteanzahl setzt die ISO 8859-1-Codierung voraus.

+1%`,
;$'¶$`];[
;
,

Probieren Sie es online aus!

Erläuterung

Dies berechnet natürlich alle Partitionen mithilfe der Zeichenfolgenverarbeitung. Die Grundidee ist, dass wir alle Partitionen generieren können, indem wir für jede ,einzeln entscheiden, ob wir die Liste dort aufteilen möchten oder nicht. Diese Art von Dingen kann in Retina durchgeführt werden, indem sie nacheinander ,abgeglichen werden und ein Ersatz verwendet wird, der beide möglichen Ausgaben liefert.

Die Eingabe fungiert als Basisfall: Die Partition, in der sich alle Elemente noch in einer einzigen Liste befinden.

+1%`,
;$'¶$`];[

Jetzt +stimmen wir wiederholt ( ) mit dem ersten ( 1) Komma ( ,) in jeder Zeile ( ) überein %(wobei diese Zeile als separate Zeichenfolge behandelt wird, die für $'und "$ 1" in der Ersetzung relevant ist ).

Dieses Komma wird ersetzt durch:

;   A semicolon. This is just a stand-in for the comma, so we know we've already
    processed it and it won't be substituted again by the next iteration.
$'  Everything after the match. This completes the first (unchanged) version of
    the current line.
¶   A linefeed. Since the next iteration will scan for all lines again, this doubles
    the number of strings we're working with.
$`  Everything before the match. This completes the second (split) version of
    the current line.
];[ A semicolon around which we split the list.

Denken Sie daran, dass alles vor und nach dem Spiel ohnehin in der Zeichenfolge verbleibt. Das vollständige Ergebnis $`;$'¶$`];[$'erklärt also, warum wir das Suffix und das Präfix in dieser Reihenfolge einfügen.

Diese Schleife stoppt, sobald alle Kommas weg sind.

;
,

Ersetzen Sie abschließend die Semikolons erneut durch Kommas, um sie dem Eingabeformat anzupassen.

Martin Ender
quelle
10

Pure Bash, 28

eval echo [${1//:/{:,]:[\}}]

Hier sind Listen durch Doppelpunkte getrennt und in eckigen Klammern angegeben. Zum Beispiel in der Frage wäre die Eingabeliste 1:2:3:4und die Ausgabe ist:

[1:2:3:4] [1:2:3]:[4] [1:2]:[3:4] [1:2]:[3]:[4] [1]:[2:3:4] [1]:[2:3]:[4] [1]:[2]:[3:4] [1]:[2]:[3]:[4]

Probieren Sie es online aus .

  • ${1//:/REPLACEMENT}ersetzt die Doppelpunkte $1durch{:,]:[\}
  • Dies erzeugt eine Klammererweiterung wie [1{:,]:[}2{:,]:[}3{:,]:[}4]
  • Die Auswertung (und vorsichtige \Flucht) bewirkt, dass die Klammerausdehnung zuletzt erfolgt und das gewünschte Ergebnis erzielt wird.

Wenn es notwendig ist, das angegebene [[ , , ...]]Format genau anzupassen, können wir dies stattdessen tun:

Pure Bash, 47

eval printf '%s\\n' ${1//, /{\\,\\ ,]\\,\\ [\}}

Probieren Sie es online aus .

Digitales Trauma
quelle
6

Pyth , 2 Bytes

./

Mit Eingabe [1, 2, 3, 4](zum Beispiel).

Erläuterung : ./ist der Partitionsoperator. Es gibt alle Unterteilungen der Eingabeliste in disjunkte Unterlisten zurück. Die Eingabe wird implizit dem Programm zugeführt.

Testen Sie es online!

Jim
quelle
6

05AB1E , 5 Bytes

Œæʒ˜Q

Probieren Sie es online aus!

Œæʒ˜Q  Main link. Argument l
Œ      Get all sublists of l
 æ     Powerset of those lists
  ʒ˜Q  Filter: Keep the lists that when flattened equal the input
kalsowerus
quelle
1
Wow, das ist eine sehr nette Antwort!
Adnan
1
@Adnan danke, ich bin auch ziemlich zufrieden damit. Obwohl es alles andere als effizient ist :)
Kalsowerus
Schöne Antwort, wenn es noch kein eingebautes gibt, +1 von mir! Verlassen dies nur für alle anderen hier in der Zukunft kommt, aber 05AB1E hat jetzt eine 2-Byte gebautet alle Partitionen zu erhalten: : Online ausprobieren.
Kevin Cruijssen
4

Python 3 , 82 72 66 Bytes

f=lambda l:[k+[l[i:]]for i in range(len(l))for k in f(l[:i])]or[l]

Probieren Sie es online aus!

-5 Bytes dank @JonathanAllan

ovs
quelle
Oh mein Gott, ich kann nicht wieder: (Ich habe tatsächlich so etwas versucht und es hat nicht funktioniert, ich muss irgendwo falsch gelaufen sein.
Jonathan Allan
1
... in diesem Fall lop 5 weitere
Jonathan Allan
1
@ JonathanAllan vielen Dank! Ich konnte ein weiteres Byte speichern , indem Sie die Wiederverwendung lam Ende
ovs
Diese Lösung gibt es hier bereits . Ich habe @feersum in TNB nach dem Posten der Frage angeschrieben, damit er die Möglichkeit hat, sie zu posten.
mbomb007
Ich habe nicht gemeint, dass du es rückgängig machen sollst, ich habe nur gemeint, dass du ihn geschlagen hast. Sie haben natürlich die Wahl.
mbomb007
4

Haskell , 59 55 49 Bytes

p[x]=[[[x]]]
p(x:r)=do a:b<-p r;[(x:a):b,[x]:a:b]

Probieren Sie es online aus!

Rekursive Lösung. Anwendungsbeispiel: p [1,2,3]Gibt zurück [[[1,2,3]],[[1,2],[3]],[[1],[2,3]],[[1],[2],[3]]].

-6 Bytes dank xnor !

Laikoni
quelle
1
Sie können die zweite Zeile mit do notation kürzer schreiben: do a:b<-p r;[(x:a):b,[x]:a:b](dies ändert die Reihenfolge der Listen).
xnor
1
Auch <*>tut genau das, was Sie wollen [\(a:b)->(x:a):b,([x]:)]<*>p r, obwohl es mehr als , doweil das erste Lambda scheint ein Muster Spiel zu müssen.
xnor
3

J , 42 Bytes

<@(</."1)~<:@#_&(][:;<@(,~"{~0 1+>./)"1)0:

Generiert alle Unterlistenpartitons, indem die Schlüssel für Partitionsunterlisten der Länge 1 erstellt und auf die Länge der Eingabeliste iteriert werden. Jede Partitionsunterliste wird dann durch Auswahl aus den Schlüsseln gebildet.

Hier ist beispielsweise der Vorgang zum Erstellen der Schlüssel für eine Liste der Länge 4.

Beispiel

Probieren Sie es online aus!

Meilen
quelle
2

Brachylog , 2 Bytes

~c

Probieren Sie es online aus!

Funktionsübermittlung, die eine Ausgabe erzeugt, indem sie als Generator fungiert. (Der TIO-Link enthält zusätzlichen Code, um daraus zu Testzwecken ein vollständiges Programm zu machen.)

Obwohl dies technisch gesehen kein eingebautes Element ist, wird es in Brachylog übrigens so häufig verwendet, dass a) es wahrscheinlich eine cEinzelbyte -Darstellung verdient und b) das eingebaute einen Parameter verwenden kann, um Aussagen über seine Eingabe zu treffen (während es bei den meisten eingebauten ein Parameter ist spricht darüber, wie die Ausgabe erzeugt wird ).

Erläuterung

~c
~     Find a value with the following properties:
 c      concatenating its elements produces {the input}

quelle
2

APL, 26 Bytes

{⊂∘⍵¨1,¨↓⍉(X⍴2)⊤⍳2*X←⍴1↓⍵}

Prüfung:

      {⊂∘⍵¨1,¨↓⍉(X⍴2)⊤⍳2*X←⍴1↓⍵} 1 2 3 4
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│┌─────┬─┐│┌───┬───┐│┌───┬─┬─┐│┌─┬─────┐│┌─┬───┬─┐│┌─┬─┬───┐│┌─┬─┬─┬─┐│┌───────┐│
││1 2 3│4│││1 2│3 4│││1 2│3│4│││1│2 3 4│││1│2 3│4│││1│2│3 4│││1│2│3│4│││1 2 3 4││
│└─────┴─┘│└───┴───┘│└───┴─┴─┘│└─┴─────┘│└─┴───┴─┘│└─┴─┴───┘│└─┴─┴─┴─┘│└───────┘│
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘

Erläuterung:

  • X←⍴1↓⍵: Xist die Länge von (der Eingabeliste), wobei das erste Element gelöscht wird
  • ⍳2*X: die Zahlen [1..2 ^ X]
  • (X⍴2)⊤: Basis-2-Darstellung dieser Zahlen mit XPositionen (dh Xselbst wird umlaufen 0).
  • ↓⍉: Drehen Sie die Matrix und teilen Sie sie entlang der Linien ( ergibt als Ergebnis eine Matrix mit den Zahlen entlang der Spalten), wodurch ein Array von Bitvektoren erhalten wird
  • 1,¨: Stellen Sie jedem Bitvektor eine 1 voran.
  • ⊂∘⍵¨: für jeden Bitvektor bei jeder 1 teilen .
Marinus
quelle
1

Python , 90 Bytes

von Ovs überfordert (etwas zu machen, von dem ich dachte, ich hätte es versucht zu arbeiten: p)

def f(a):r=[[a]];i=len(a)-1;exec("for s in f(a[:i]):s+=[a[i:]];r+=[s]\ni-=1\n"*i);return r

Eine rekursive Funktion, die die Liste der Partitionen aus Slices der Eingabe aufbaut, wobei das Ende erreicht wird, wenn die Slices die Länge 1 haben.

Probieren Sie es online aus!

Das execspart 4 Bytes über eine whileoder 3 Bytes über eine forSchleife (unten), da es nur zwei \ns statt zwei Einrückungsstufen bedeutet, sodass sich die gesamte Funktion in einer Zeile befindet (während die Reihenfolge des Aufteilens keine Rolle spielt).

def f(a):
 r=[[a]]
 for i in range(1,len(a)):
  for s in f(a[:i]):s+=[a[i:]];r+=[s]
 return r
Jonathan Allan
quelle
1

Haskell, 59 Bytes

x#[]=[[[x]]]
x#(a:b)=[(x:a):b,[x]:a:b]
foldr((=<<).(#))[[]]
Alephalpha
quelle
1

Ruby , 62 57 Bytes

->l{(0..2**l.size).map{|x|l.chunk{1&x/=2}.map &:last}|[]}

Probieren Sie es online aus!

Wie es funktioniert:

  • Die Anzahl der Partitionen beträgt 2 ^ (n-1): Ich iteriere mit Binärzahlen in diesem Bereich, nehme die Gruppen von Nullen und Einsen und ordne sie als Teilmengen der Anfangsliste zu.
  • Anstatt mit dem Bereich herumzuspielen, mache ich ihn doppelt und verwerfe Duplikate am Ende. Jetzt kann ich auch die erste Binärziffer verwerfen und die Chunk-Funktion verkürzen.
GB
quelle
0

JavaScript (ES6), 87 Byte

([e,...a],b=[],c=[e],d=[...b,c])=>1/a[0]?[...f(a,b,[...c,a[0]]),...f(a,d,[a[0]])]:[d]

Erläuterung: Ist bdie Liste der vorherigen Unterlisten, cist die aktuelle Unterliste (die als erstes Element des Arrays beginnt, da diese in der ersten Unterliste enthalten sein muss), während ddie Liste aller Unterlisten ist. Der Rest der Array-Elemente wird dann rekursiv verarbeitet. In jedem Fall gibt es zwei Möglichkeiten: Entweder wird das nächste Element an die aktuelle Unterliste angehängt, oder die aktuelle Unterliste wird abgeschlossen und das nächste Element startet eine neue Unterliste. Die rekursiven Ergebnisse werden dann miteinander verkettet. Wenn das Array erschöpft ist, ist die Liste der Liste aller Unterlisten das Ergebnis.

Neil
quelle
0

APL (NARS) 38 Zeichen, 76 Bytes

{k←↑⍴⍵⋄x←11 1‼k k⋄y←⍵⋄∪{x[⍵;]⊂y}¨⍳↑⍴x}

Dies verwendet die Nars-Funktion 11 1‼ kk, ist aber sehr langsam und für ein arg-Array mit 9 Elementen bereits unbrauchbar ...

  P3←{k←↑⍴⍵⋄x←11 1‼k k⋄y←⍵⋄∪{x[⍵;]⊂y}¨⍳↑⍴x}

  ⍴∘P3¨{1..⍵}¨⍳8
1  2  4  8  16  32  64  128 
  P3 'abcd'
abcd    abc d    ab cd    a bcd    ab c d    a bc d    a b cd    a b c d

Dies ist die Funktion, die das eingebaute nicht verwendet:

r←h w;k;i
   r←⊂,⊂w⋄k←↑⍴w⋄i←1⋄→B
A: r←r,(⊂⊂,i↑w),¨h i↓w⋄i+←1
B: →A×⍳i<k

  h 'abcd'
abcd    a bcd    a b cd    a b c d    a bc d    ab cd    ab c d    abc d
  ⍴∘h¨{1..⍵}¨⍳8
2  4  8  16  32  64  128 

Wir sehen den Typ jedes Ergebnisses:

  o h ,1
┌──────┐
│┌1───┐│
││┌1─┐││
│││ 1│││
││└~─┘2│
│└∊───┘3
└∊─────┘
  o h 1 2
┌2───────────────────┐
│┌1─────┐ ┌2────────┐│
││┌2───┐│ │┌1─┐ ┌1─┐││
│││ 1 2││ ││ 1│ │ 2│││
││└~───┘2 │└~─┘ └~─┘2│
│└∊─────┘ └∊────────┘3
└∊───────────────────┘

Ich weiß nicht wie es funktioniert, es ist nur ein heuristischer Versuch ...

Möglicherweise mache ich einen Fehler; Beide Funktionen bilden die Partitionen der Liste unabhängig von der Eingabe und nicht nur 1 2 ... n.

RosLuP
quelle
0

Axiom, 251 Bytes

C==>concat;A==>List Any;px(a:A):A==(k:=#a;r:=copy[a];k<=1=>r;i:=1;repeat(i>=k=>break;x:=a.(1..i);y:=a.((i+1)..k);z:=px(y);t:=[x,z.1];for j in 2..#z repeat(w:=(z.j)::A;m:=#w;v:=[x];for q in 1..m repeat v:=C(v,w.q);t:=C(t,[v]));r:=C(r,copy t);i:=i+1);r)

Wenn jemand etwas Besseres findet ... ungof und teste:

pp(a:List Any):List Any==
  k:=#a;r:=copy[a];k<=1=>r;i:=1
  repeat
    i>=k=>break
    x:=a.(1..i);y:=a.((i+1)..k);z:=pp(y);
    t:=[x,z.1]
    for j in 2..#z repeat
           w:=(z.j)::List Any
           m:=#w; v:=[x]
           for q in 1..m repeat 
                       v:=concat(v,w.q);
           t:=concat(t,[v])
    r:=concat(r,copy t);
    i:=i+1
  r

(7) -> px []
 (7)  [[]]
                                                           Type: List Any
(8) -> px [1]
 (8)  [[1]]
                                                           Type: List Any
(9) -> px [1,2]
 (9)  [[1,2],[[1],[2]]]
                                                           Type: List Any
(10) -> px [1,2,3]
 (10)  [[1,2,3],[[1],[2,3]],[[1],[2],[3]],[[1,2],[3]]]
                                                           Type: List Any
(11) -> px [1,2,3,4,5,6]
 (11)
[[1,2,3,4,5,6], [[1],[2,3,4,5,6]], [[1],[2],[3,4,5,6]],
 [[1],[2],[3],[4,5,6]], [[1],[2],[3],[4],[5,6]], [[1],[2],[3],[4],[5],[6]],
 [[1],[2],[3],[4,5],[6]], [[1],[2],[3,4],[5,6]], [[1],[2],[3,4],[5],[6]],
 [[1],[2],[3,4,5],[6]], [[1],[2,3],[4,5,6]], [[1],[2,3],[4],[5,6]],
 [[1],[2,3],[4],[5],[6]], [[1],[2,3],[4,5],[6]], [[1],[2,3,4],[5,6]],
 [[1],[2,3,4],[5],[6]], [[1],[2,3,4,5],[6]], [[1,2],[3,4,5,6]],
 [[1,2],[3],[4,5,6]], [[1,2],[3],[4],[5,6]], [[1,2],[3],[4],[5],[6]],
 [[1,2],[3],[4,5],[6]], [[1,2],[3,4],[5,6]], [[1,2],[3,4],[5],[6]],
 [[1,2],[3,4,5],[6]], [[1,2,3],[4,5,6]], [[1,2,3],[4],[5,6]],
 [[1,2,3],[4],[5],[6]], [[1,2,3],[4,5],[6]], [[1,2,3,4],[5,6]],
 [[1,2,3,4],[5],[6]], [[1,2,3,4,5],[6]]]
                                                           Type: List Any
(12) -> [[i,#px i] for i in [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5,6]] ]
 (12)
[[[],1],[[1],1],[[1,2],2],[[1,2,3],4],[[1,2,3,4],8],[[1,2,3,4,5,6],32]]
                                                      Type: List List Any
(13) -> [#px(i) for i in [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5,6]] ]
 (13)  [1,1,2,4,8,32]
                                            Type: List NonNegativeInteger

Wenn dies zu viel Platz ist, sagen Sie das und ich entferne Beispiele ...

RosLuP
quelle