Zielsetzung
Generieren Sie die ursprüngliche verschlüsselte Liste aus den Bewegungen, die eine Einfügungssortierung ausführen würde, um sie zu sortieren. Die ursprüngliche Liste enthält alle Zahlen von 0
bis N-1
(einschließlich), wobei N
die Größe der Eingabe ist.
Eingang
Eine Liste mit den erforderlichen Schritten zum Sortieren der Liste. Jeder Wert stellt die Anzahl der Slots dar, die um die ursprüngliche (verschlüsselte) Nummer verschoben wurden, um sich an der richtigen Position zu befinden. Beachten Sie, dass dieser Vorgang von links nach rechts verläuft.
Der Wert an der (0-indizierten) Position i
in der Eingabeliste liegt zwischen 0
und i
einschließlich.
Sie müssen keine ungültigen Eingaben verarbeiten. In diesem Fall ist jedes Verhalten akzeptabel (Absturz, Endlosschleife usw.).
Ausgabe
Die verschlüsselte Liste
Schritt für Schritt, um die Züge zu generieren
Scrambled List | Moves to sort
[4,0,2,1,3,5] | [0, , , , , ] #4 stay in place
[4,0,2,1,3,5] | [0,1, , , , ] #0 is moved 1 slot to the left
[0,4,2,1,3,5] | [0,1,1, , , ] #2 is moved 1 slot
[0,2,4,1,3,5] | [0,1,1,2, , ] #1 is moved 2 slot
[0,1,2,4,3,5] | [0,1,1,2,1, ] #3 is moved 1 slot
[0,1,2,3,4,5] | [0,1,1,2,1,0] #5 is in the right place already
[0,1,2,3,4,5]
Also, für die Eingabe muss [0,1,1,2,1,0]
Ihr Programm ausgeben [4,0,2,1,3,5]
.
Beachten Sie, dass sich die Bewegungen nicht an der Position in der (endgültigen) sortierten Liste befinden, sondern im sortierten Segment (fettgedruckter Abschnitt).
Testfälle
[0,0,0] -> [0,1,2]
[0,1,0,1] -> [1,0,3,2]
[0,0,0,0,0,5] -> [1,2,3,4,5,0]
[0,1,2,3] -> [3,2,1,0]
[0,1,1,1] -> [3,0,1,2]
[0,1,1,2,1,0] -> [4,0,2,1,3,5]
Gewinnen
Das ist Code-Golf , also gewinnt die kürzeste Antwort.
quelle
Antworten:
Gelee , 12 Bytes
Probieren Sie es online!
Erläuterung
Grundsätzlich können wir die beiden Listen (die Eingabe und die Ausgabe) als Codierung einer Ganzzahl betrachten. Die Eingabe codiert eine Ganzzahl auf faktorieller Basis, und die Ausgabe codiert eine Ganzzahl als Permutation. Zum Glück verfügt Jelly über integrierte Funktionen, die diesen beiden Codierungen bereits sehr nahe kommen. Sie müssen also nur kleine Codestücke schreiben, um sie in eine Ganzzahl umzuwandeln, und dann wieder in die andere Codierung.
Im Fall der faktoriellen Basis können wir beobachten, dass das erste Element der Liste 0 sein muss, das zweite 0 oder 1 sein kann, das dritte 0/1/2 sein muss und so weiter. Daher müssen wir die Eingabe umkehren, um ihre Elemente in die normale Schreibreihenfolge für die Basisumwandlung zu bringen.
Darüber hinaus müssen zwei Anpassungen vorgenommen werden, damit die relative Reihenfolge der Fakultätskonvertierung und der Permutationskonvertierung mit der von der Einfügesortierung verwendeten Operation übereinstimmt: Umkehren der Reihenfolge der Permutationen und Umkehren der Reihenfolge der Ausgabeliste. Das Umkehren der Ausgabeliste ist einfach und erfordert nur einen
U
am Ende des Programms. Um die Reihenfolge der Permutationen umzukehren, subtrahieren wir von der Fakultät der Eingangslänge (dies funktioniert, weil die Basisfakultät eine Zahl im Bereich von 0 bis (Länge! -1) ergibt, während die Permutationen von Jelly von 1 bis Länge nummeriert werden! (Erzeugen eines impliziten Off-by-One, der das Off-by-One auslöscht, das Sie normalerweise erhalten, wenn Sie einen Permutationsindex von einer Fakultät subtrahieren).Jelly , 9 Bytes, in Zusammenarbeit mit @JonathanAllan
Diese Programmversion ist sehr ähnlich, verwendet jedoch eine andere Methode, um die Reihenfolge der Permutationen umzukehren. Das Negieren der Eingabe mit
N
genügt, umœ?
die Reihenfolge in umgekehrter Reihenfolge zu behandeln. Ansonsten funktioniert es identisch zum vorherigen Programm.Probieren Sie es online!
quelle
Æ¡
undœ?
Atome dafür funktionieren würden (ich hatte bereits früher versucht, sie für diese Herausforderung zu verwenden - ich war so nah dran, ich brauchte nur die daL!
drin).UÆ¡Nœ?L’U
weil ich implementiertœ?
(und ähnlich), um modular zu handeln (als ob sie Jelly-Listen verwenden würden). DasN
nur indiziert mit dem negativen Wert. Hinweis: Ich wechselteJ
zuL
- das ist nur gegeben , weil eine Reihe macht es einen Bereich unter der Motorhaube sowieso).Mathematica, 92 Bytes
Reine Funktion, die eine Liste nichtnegativer Ganzzahlen als Eingabe verwendet und eine Liste nichtnegativer Ganzzahlen zurückgibt. Der obige Code enthält ein
©
, was falsch ist: Es ist ein Platzhalter für das 3-Byte-Symbol U + F3DE, das Mathematica durch einen Kreis mit einem Punkt darstellt und das die Zusammensetzung von Permutationen darstellt.c=Cycles@{#}&
definiert eine Funktion, die eine Liste von Ganzzahlen in einCycles
Objekt konvertiert, das eine Permutation darstellt; Beispielsweisec[{3,4}]
handelt es sich bei den Transpositionsaustauschelementen 3 und 4 um eine Liste.c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]
Nimmt die Eingabeliste und generiert die Permutationen, die zum Rückgängigmachen der Einfügesortierung erforderlich sind. Dann werdenc@{}©##&@@
alle diese Permutationen zusammengesetzt, beginnend mit der Identitätspermutationc@{}
. SchließlichPermute[Range[l=Length@#]-1,...]
gilt diese Permutation auf die 0-indizierte Liste der entsprechenden Länge.quelle
@{#}&)@{}©##&@@
sieht gruselig aus.Python 2,
7968 BytesVielen Dank an Krazor für das Speichern von 10 Bytes
Vielen Dank an TuukkaX für das Speichern von 1 Byte
Funktioniert durch Generieren der Bewegungen in umgekehrter Reihenfolge
quelle
a=input();b=range(len(a));print[b.pop(j-a[j]) for j in b[::-1]][::-1]
. Listenverständnisse ftw!for
, also mach das 65. Ich schätze: DJavaScript (ES6),
696563 BytesEs ist ärgerlich, dass sowohl die Eingabe als auch die Ausgabe in der falschen Reihenfolge erfolgen. Bearbeiten: 4 Bytes dank @Arnauld gespeichert. 2 Bytes gespart dank @ETHproductions.
quelle
i
, oder?i
...o=>+b.splice(~o,1)
JavaScript (ES6),
73-71Byte2 Bytes gespart dank ETHproductions
Testfälle
Code-Snippet anzeigen
quelle
a=m.map(_=>j++,j=0)
, aber das ist die gleiche Länge und ich bin sicher, dass Sie es bereits versucht haben.j
zua.length
als vielmehra.length-1
und erfordern würdea.splice(--j,0,a.splice(j-m[j],1)[0])
)+a.splice(j-m[j--],1)
Haskell , 85 Bytes
Probieren Sie es online! Anwendungsbeispiel:
f [0,1,1,2,1,0]
Erträge[4,0,2,1,3,5]
.f x
ruft die Funktion#
mitx
umgekehrter Liste und einer Liste auf[length x - 1, length x - 2, ... , 0]
.(n:r)#l
führt die umgekehrte Einfügesortierung durch, indem rekursiv dasn
th-Element entfernt wirdl
, wobeil!!n
dasn
th-Element undtake n l++drop(n+1)l
die Listel
mit dem entferntenn
th-Element erhalten werden.quelle
Perl, 61 Bytes
Die Ausgabe endet im Array @o. Beispiel mit Eingabearray als Kommandozeilenargumente:
quelle
Ruby, 49 Bytes
Führt die "umgekehrte Einfügung" in der Liste aus, beginnend mit der größten Nummer.
quelle