Gestern habe ich diese Frage zu Riffle Shuffles gestellt. Es scheint, dass die gestrige Frage etwas zu schwierig war, daher ist diese Frage eine verwandte, aber viel einfachere Aufgabe.
Heute werden Sie gefragt, ob eine Permutation tatsächlich ein Riffle-Shuffle ist. Unsere Definition von Riffle Shuffle wurde von unserer letzten Frage übernommen:
Der erste Teil des Shuffle ist die Kluft. In der Divide-Partition wird das Kartenspiel in zwei Teile geteilt. Die beiden Unterabschnitte müssen fortlaufend sein, sich gegenseitig ausschließen und erschöpfend sein. In der realen Welt möchten Sie Ihre Partition so gleichmäßig wie möglich gestalten. Bei dieser Herausforderung spielt dies jedoch keine Rolle. Alle Partitionen, einschließlich entarteter Partitionen (eine Partition ist leer), werden gleichermaßen berücksichtigt.
Nach der Partitionierung werden die Karten so zusammengefügt, dass die relative Reihenfolge der Karten in der Partition erhalten bleibt, in der sie Mitglied sind . Wenn die Karte zum Beispiel A vor Karte B im Deck und Karten A und B sind in der gleichen Partition, Karte A muss vor der Karte sein B im Endergebnis, auch wenn die Anzahl der Karten zwischen ihnen erhöht. Wenn sich A und B in unterschiedlichen Partitionen befinden, können sie im Endergebnis unabhängig von ihrer Startreihenfolge in beliebiger Reihenfolge sein.
Jedes Riffle-Shuffle kann dann als eine Permutation des ursprünglichen Kartenstapels angesehen werden. Zum Beispiel die Permutation
1,2,3 -> 1,3,2
ist ein Riffle Shuffle. Wenn Sie das Deck so teilen
1, 2 | 3
Wir sehen, dass jede Karte in 1,3,2
der Partition dieselbe relative Reihenfolge zu jeder anderen Karte in der Partition hat. 2
ist immer noch hinterher 1
.
Andererseits ist die folgende Permutation kein Riffle-Shuffle.
1,2,3 -> 3,2,1
Wir können dies sehen, weil für alle zwei (nicht-trivialen) Partitionen
1, 2 | 3
1 | 2, 3
Es gibt ein Paar Karten, deren relative Reihenfolge nicht eingehalten wird. In der ersten Partition 1
und 2
ändern Sie ihre Reihenfolge, während in der zweiten Partition 2
und 3
ändern Sie ihre Reihenfolge.
Aufgabe
Bestimmen Sie bei einer Permutation mit einer vernünftigen Methode, ob es sich um ein gültiges Riffle Shuffle handelt. Sie sollten zwei unterschiedliche konstante Werte ausgeben, einen für "Ja, das ist ein Riffle-Shuffle" und einen für "Nein, das ist kein Riffle-Shuffle".
Dies ist Codegolf, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.
Testfälle
1,3,2 -> True
3,2,1 -> False
3,1,2,4 -> True
2,3,4,1 -> True
4,3,2,1 -> False
1,2,3,4,5 -> True
1,2,5,4,3 -> False
5,1,4,2,3 -> False
3,1,4,2,5 -> True
2,3,6,1,4,5 -> False
quelle
0
für falsch, aber eine ganze Zahl[1, +∞)
für wahr?[3,1,4,2,5]
.[2,3,6,1,4,5]
.[0, ..., n-1]
statt[1, ..., n]
als Eingabe nehmen?Antworten:
JavaScript (ES6), 47 Byte
Nimmt die Eingabe als Array von Ganzzahlen. Gibt einen Booleschen Wert zurück.
Testfälle
Code-Snippet anzeigen
Wie?
Das Eingabearray A ist ein gültiges Riffle-Shuffle, wenn es aus höchstens zwei verschiedenen verschachtelten Folgen aufeinanderfolgender ganzer Zahlen besteht.
Die Herausforderungsregeln geben an, dass wir eine Permutation von [1 ... N] erhalten . Wir müssen also nicht zusätzlich prüfen, ob die sortierte Vereinigung dieser Sequenzen tatsächlich zu einem solchen Bereich führt.
Wir verwenden einen auf A [0] initialisierten Zähler x und einen anfangs undefinierten Zähler y .
Für jeden Eintrag z in A beginnend mit dem 2. Eintrag :
quelle
Haskell , 41 Bytes
Probieren Sie es online!
Überprüft, ob die mit sich selbst verkettete Liste die Nummern
0..n-1
in der angegebenen Reihenfolge als Teilsequenz enthält .quelle
Haskell , 43 Bytes
s
Nimmt eine Liste von Ganzzahlen wie in den OP-Beispielen und gibt a zurückBool
.Probieren Sie es online!
Wie es funktioniert
x
derp
Reihe nach und prüft, ob es das erste Element der zweiten Partition des Shuffle sein kann. Kehrt dannor
zurück,True
wenn einer der Schecks warTrue
.filter
)p
in Elemente unterteilt, die kleiner und größer als (oder gleich) sindx
, verkettet und überprüft, ob die resultierende Liste[1..length p]
, dh die Elemente, in der richtigen Reihenfolge sind.[1..length p]
durchgeführt, indem festgestellt wird, ob das Ergebnis streng kleiner als die unendliche Liste ist[1..] == [1,2,3,etc.]
, was für jede Permutation dasselbe Ergebnis ergibt.quelle
Jelly ,
136 BytesProbieren Sie es online!
Alternative Version, Challenge nach Datum, 5 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
Python 2 , 39 Bytes
Probieren Sie es online!
Nimmt die Liste 0-indiziert und gibt sie per Exit-Code aus.
quelle
Brachylog , 9 Bytes
Probieren Sie es online!
Das Prädikat ist erfolgreich, wenn die Eingabe ein Riffle-Shuffle darstellt, und schlägt fehl, wenn dies nicht der Fall ist. Dies bedeutet unter anderem, dass bei Ausführung des Prädikats ein vollständiger Programmerfolg ausgegeben wird
true.
und ein Fehler ausgegeben wirdfalse.
. Die Eingabe wird als Liste aller Arten von Elementen interpretiert und als sortierte Permutation von sich selbst interpretiert.Ich habe das Gefühl, dass es etwas gibt, dessen Geist
⊆ᵐ
anstelle des 4-Byte- "Sandwich" -Konstrukts funktionieren sollte⟨⊆⊇⟩
.quelle
Python 2 ,
756047 Bytesdanke an Dennis für -13 bytes
Probieren Sie es online!
Die Ausgabe erfolgt über den Exit-Code.
quelle
Ruby , 35 Bytes
Probieren Sie es online!
Wie?
l & [*1..a] | l
Wendet eine Schnittmenge und dann eine Vereinigung an: Ermitteln Sie zuerst die Elementel
, die vorhanden sind,<=a
und fügen Sie dann die übrigen Elemente hinzu,l
ohne die Reihenfolge zu ändern. Wenn a die gesuchte Zahl ist, entspricht dieser Vorgang dem Sortierenl
.quelle
Sauber ,
5655 BytesProbieren Sie es online!
quelle
Pyth, 5 Bytes
Testsuite
Überprüft, ob die Liste der doppelten Eingaben eine sortierte Version von sich selbst als Teilsequenz enthält.
Dank an Erik den Outgolfer für 1 Byte, der implizite Eingaben besser ausnutzt
+QQ
als*2Q
.quelle
}SQy+
. Es wird erweitert um}SQy+QQ
.Pyth , 9 Bytes
Testsuite.
3 Bytes dank isaacg gespart .
Pyth , 14 Bytes
Probieren Sie es hier aus! oder Überprüfen Sie alle Testfälle.
Ausgänge
True
undFalse
für Riffle-Shuffle bzw. Nicht-Riffle-Shuffle.Wie?
quelle
<#0
kann durch-
2 weitere Bytes ersetzt werden.Schale , 7 Bytes
Testsuite!
quelle
Perl, 28 Bytes
Enthält
+1
füra
Eingang auf STDIN, 1 basiert
Uses xnor-Algorithmus
quelle
C (gcc) , 61 Bytes
Probieren Sie es online!
quelle