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!
[...]
im Ausgabeformat weglassen ? (Solange Partitionen klar voneinander getrennt sind, z. B. durch Zeilenvorschübe.):
als Listentrennzeichen verwendet, aber in der Ausgabe werden Partitionen selbst nicht in ein zusätzliches Paar von eingeschlossen[...]
.[
und die letzte]
Zeile aus jeder Zeile entfernen?Antworten:
Gelee , 2 Bytes
Probieren Sie es online aus!
quelle
Netzhaut ,
2719 BytesDie Byteanzahl setzt die ISO 8859-1-Codierung voraus.
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.
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:
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.
quelle
Pure Bash, 28
Hier sind Listen durch Doppelpunkte getrennt und in eckigen Klammern angegeben. Zum Beispiel in der Frage wäre die Eingabeliste
1:2:3:4
und die Ausgabe ist:Probieren Sie es online aus .
${1//:/REPLACEMENT}
ersetzt die Doppelpunkte$1
durch{:,]:[\}
[1{:,]:[}2{:,]:[}3{:,]:[}4]
\
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
Probieren Sie es online aus .
quelle
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!
quelle
05AB1E , 5 Bytes
Probieren Sie es online aus!
quelle
.œ
: Online ausprobieren.Python 3 ,
827266 BytesProbieren Sie es online aus!
-5 Bytes dank @JonathanAllan
quelle
l
am EndeHaskell ,
595549 BytesProbieren 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 !
quelle
do a:b<-p r;[(x:a):b,[x]:a:b]
(dies ändert die Reihenfolge der Listen).<*>
tut genau das, was Sie wollen[\(a:b)->(x:a):b,([x]:)]<*>p r
, obwohl es mehr als ,do
weil das erste Lambda scheint ein Muster Spiel zu müssen.J , 42 Bytes
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.
Probieren Sie es online aus!
quelle
J ,
2624 BytesProbieren Sie es online aus!
quelle
Brachylog , 2 Bytes
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
c
Einzelbyte -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
quelle
APL, 26 Bytes
Prüfung:
Erläuterung:
X←⍴1↓⍵
:X
ist 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 mitX
Positionen (dhX
selbst wird umlaufen0
).↓⍉
: 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 wird1,¨
: Stellen Sie jedem Bitvektor eine 1 voran.⊂∘⍵¨
: für jeden Bitvektor⍵
bei jeder 1 teilen .quelle
Haskell , 45 Bytes
Probieren Sie es online aus!
Ich habe diese Lösung vor einiger Zeit gefunden, als ich über einen Haskell-Tipp nachgedacht habe .
quelle
Python , 90 Bytes
von Ovs überfordert (etwas zu machen, von dem ich dachte, ich hätte es versucht zu arbeiten: p)
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
exec
spart 4 Bytes über einewhile
oder 3 Bytes über einefor
Schleife (unten), da es nur zwei\n
s statt zwei Einrückungsstufen bedeutet, sodass sich die gesamte Funktion in einer Zeile befindet (während die Reihenfolge des Aufteilens keine Rolle spielt).quelle
Python 3 , 67 Bytes
Probieren Sie es online aus!
quelle
Haskell, 59 Bytes
quelle
Ruby ,
6257 BytesProbieren Sie es online aus!
Wie es funktioniert:
quelle
JavaScript (ES6), 87 Byte
Erläuterung: Ist
b
die Liste der vorherigen Unterlisten,c
ist die aktuelle Unterliste (die als erstes Element des Arrays beginnt, da diese in der ersten Unterliste enthalten sein muss), währendd
die 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.quelle
APL (NARS) 38 Zeichen, 76 Bytes
Dies verwendet die Nars-Funktion 11 1‼ kk, ist aber sehr langsam und für ein arg-Array mit 9 Elementen bereits unbrauchbar ...
Dies ist die Funktion, die das eingebaute nicht verwendet:
Wir sehen den Typ jedes Ergebnisses:
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.
quelle
Axiom, 251 Bytes
Wenn jemand etwas Besseres findet ... ungof und teste:
Wenn dies zu viel Platz ist, sagen Sie das und ich entferne Beispiele ...
quelle