Kann das Array nicht gemischt werden?

15

Hintergrund

Sehr geübte Kartenverarbeiter sind in der Lage, ein Kartenspiel perfekt zu halbieren und dann die Karten perfekt zu verschachteln. Wenn sie mit einem sortierten Deck beginnen und diese Technik 52 Mal hintereinander fehlerfrei ausführen, wird das Deck in der sortierten Reihenfolge wiederhergestellt. Ihre Herausforderung besteht darin, einem Kartenspiel ein ganzzahliges Array zuzuweisen und zu bestimmen, ob es nur mit Faro-Shuffles sortiert werden kann.

Definition

Mathematisch gesehen ist ein Faro-Shuffle eine Permutation auf 2 n Elementen (für jede positive ganze Zahl n ), die das Element in Position i (1-indiziert) zu Position 2 i (mod 2 n +1) bringt . Wir möchten auch in der Lage sein, Listen mit ungerader Länge zu verarbeiten. In diesem Fall fügen Sie einfach ein Element am Ende der Liste hinzu (einen Joker, falls Sie ein handliches Element haben) und Faro mischt die neue Liste wie oben beschrieben, ignoriert sie jedoch das hinzugefügte Dummy-Element, wenn die Reihenfolge der Liste überprüft wird.

Tor

Schreiben Sie ein Programm oder eine Funktion, die eine Liste von ganzen Zahlen aufnimmt und eine Wahrheit zurückgibt oder ausgibt, wenn eine bestimmte Anzahl von Faro-Shuffles dazu führen würde, dass diese Liste in nicht absteigender Reihenfolge sortiert wird (auch wenn diese Zahl Null ist - kleine Listen sollten eine Wahrheit ergeben). Andernfalls wird ein Fehler zurückgegeben oder ausgegeben.

Beispiele

[1,1,2,3,5,8,13,21]  => True
[5,1,8,1,13,2,21,3] => True
[9,36,5,34,2,10,1] => True
[1,0] => True
[0] => True
[] => True
[3,2,1] => True
[3,1,2] => False
[9,8,7,6,5,4,3,2,1,0] => True
[9,8,7,6,5,4,3,2,0,1] => False
[3,1,4,1,5,9,2,6,9] => False
[-1,-1,-1,-2] => True

Wertung

Dies ist Code-Golf, also gewinnt die kürzeste Quelle in Bytes.

code-golf array-manipulation permutations Quintopie
quelle
Um Verwechslungen mit anderen Kartenführern zu vermeiden, sollte beachtet werden, dass es zwei Arten von Faro-Shuffles gibt. Ein In-Shuffle und ein Out-Shuffle . Die hier beschriebene Methode ist ein In-Shuffle. Interessanterweise werden nur 8 Ausmischungen benötigt, um ein Deck wieder in die ursprüngliche Reihenfolge zu bringen. Weitere
Informationen
Ist das nicht einfach "N + 1-mal gemischt und überprüft, ob eine der Listen auf dem Weg sortiert ist"?
Lirtosiast
Tatsächlich ist n-mal ausreichend, da 2-maliges Auffinden aller möglichen Permutationen garantiert ist, aber Sie erhalten in den ersten n mindestens eine aufsteigende oder absteigende Reihenfolge.
Quintopia
1
Verbunden. Verbunden.
Martin Ender
1
bleibt das erste element nicht immer an erster stelle?
Eumel,

Antworten:

3

Pyth - 26 25 24 Bytes

Verwendet die kumulative Reduzierung, um Faro Shuffle mehrmals anzuwenden und alle Ergebnisse beizubehalten. Dann ordnet es es durch und prüft, ob sie beim Sortieren invariant sind, dann verwendet es die Summe, um zu prüfen, ob irgendwelche wahr sind. Gibt eine positive oder Null zurück.

smSI-db.usC_c2NQsC.tc2Qb

Test Suite .

Maltysen
quelle
3

MATL , 41 Bytes

itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx

Die Ausgabe ist 1oder 0.

Erläuterung

i              % get input array
tn2\           % is size odd?
?              % if that's the case
  YNh          % concat NaN at the end
]              % end if
tn             % get size of input array
t1+:           % vector 1:n+1, where n is input size, so loop will be entered even with []
"              % for loop
  x[]2e!PY)    % delete result from previous iteration and do the shuffling
  ttZN~)       % remove NaN, if there's any
  tS=A         % check if array is sorted
  t.           % copy the result. If true, break loop
]              % end for
wx             % remove unwanted intermediate result

Beispiel

>> matl itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx
> [1,1,2,3,5,8,13,21]
1
Luis Mendo
quelle