Einfügesortierung umkehren

19

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 0bis N-1(einschließlich), wobei Ndie 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 iin der Eingabeliste liegt zwischen 0und ieinschließ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 , also gewinnt die kürzeste Antwort.

Stange
quelle
1
Darf das Programm auch die Länge der Liste als Eingabe nehmen?
mbomb007
@ mbomb007 nein.
Rod
Können wir stattdessen (n-1) Schritte verwenden? Der erste ist unnötig, da er immer Null ist.
GB
@ GB sicher, solange die Ausgabe richtig ist, können Sie einen beliebigen Algorithmus verwenden
Rod

Antworten:

14

Gelee , 12 Bytes

L!_UÆ¡$œ?J’U

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.

L!_UÆ¡$œ?J’U
   U           Reverse {the input}
    Æ¡         and convert from base factorial to integer;
  _   $        subtract that from
L!             the factorial of the length of {the input};
       œ?      then take the nth permutation of
         J     [1,2,...,l], where l is the length of {the input},
          ’    subtract 1 from every elevent,
           U   and reverse it

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 Uam 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

UÆ¡Nœ?J’U

Diese Programmversion ist sehr ähnlich, verwendet jedoch eine andere Methode, um die Reihenfolge der Permutationen umzukehren. Das Negieren der Eingabe mit Ngenügt, um œ?die Reihenfolge in umgekehrter Reihenfolge zu behandeln. Ansonsten funktioniert es identisch zum vorherigen Programm.

Probieren Sie es online!


quelle
4
O_O Was für eine Zauberei ist das?
DLosc
Oh, schön - ich wusste, dass meine Æ¡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 da L!drin).
Jonathan Allan
Hervorragender Code!
Greg Martin
1
In der Tat können Sie es in 9 Bytes mit tun, UÆ¡Nœ?L’Uweil ich implementiert œ?(und ähnlich), um modular zu handeln (als ob sie Jelly-Listen verwenden würden). Das Nnur indiziert mit dem negativen Wert. Hinweis: Ich wechselte Jzu L- das ist nur gegeben , weil eine Reihe macht es einen Bereich unter der Motorhaube sowieso).
Jonathan Allan
6

Mathematica, 92 Bytes

Permute[Range[l=Length@#]-1,(c=Cycles@{#}&)@{}©##&@@c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]&

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 ein CyclesObjekt konvertiert, das eine Permutation darstellt; Beispielsweise c[{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 werden c@{}©##&@@alle diese Permutationen zusammengesetzt, beginnend mit der Identitätspermutation c@{}. Schließlich Permute[Range[l=Length@#]-1,...]gilt diese Permutation auf die 0-indizierte Liste der entsprechenden Länge.

Greg Martin
quelle
1
Was kein eingebautes ?! Sicherlich ...
Jonathan Allan
3
@{#}&)@{}©##&@@sieht gruselig aus.
Yytsi
6

Python 2, 79 68 Bytes

Vielen Dank an Krazor für das Speichern von 10 Bytes

Vielen Dank an TuukkaX für das Speichern von 1 Byte

a=input();b=range(len(a));print[b.pop(j-a[j])for j in b[::-1]][::-1]

Funktioniert durch Generieren der Bewegungen in umgekehrter Reihenfolge

Mathe-Junkie
quelle
2
Mach das 66 ! Wie wäre es : a=input();b=range(len(a));print[b.pop(j-a[j]) for j in b[::-1]][::-1]. Listenverständnisse ftw!
FMaz
1
@Krazor Du hast ein Leerzeichen, das vorher entfernt werden könnte for, also mach das 65. Ich schätze: D
Yytsi
@Krazor Es stellte sich heraus, dass das Listenverständnis nicht ganz funktioniert hat, aber mir hat die Idee gefallen, b [:: - 1] zu verwenden!
Math Junkie
Auf keinen Fall? Ich habe mit Handy kommentiert, vielleicht habe ich etwas falsch geschrieben. Welcher Teil funktioniert nicht? Für mich hat es richtig interpretiert und alle Testfälle erfüllt.
FMaz
@Krazor Oh hoppla, nein du hast recht. Ich bin derjenige, der es beim Testen falsch geschrieben hat.
Math Junkie
5

JavaScript (ES6), 69 65 63 Bytes

a=>a.reverse(b=[...a.keys()]).map(o=>+b.splice(~o,1)).reverse()

Es 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.

Neil
quelle
Ich habe immer noch versucht, einen besseren Weg zu finden, aber Sie waren viel schneller. Schön!
Arnauld
1
Sie brauchen nicht i, oder?
Arnauld
@Arnauld Anscheinend nicht. Zunächst habe ich versucht, die Python-Antwort zu verstehen, und gerade erst ist mir aufgefallen, dass sie nicht wirklich verwendet wird i...
Neil,
1
Easy -2:o=>+b.splice(~o,1)
ETHproductions
3

JavaScript (ES6), 73-71 Byte

2 Bytes gespart dank ETHproductions

m=>(a=m.map((_,i)=>j=i)).map(_=>a.splice(j,0,+a.splice(j-m[j--],1)))&&a

Testfälle

Arnauld
quelle
Gute Möglichkeit, Länge und Reichweite gleichzeitig zu ermitteln. Ich wollte vorschlagen a=m.map(_=>j++,j=0), aber das ist die gleiche Länge und ich bin sicher, dass Sie es bereits versucht haben.
ETHproductions
@ETHproductions Du hast Recht: Ich habe es auch versucht. :-) (Es kann sich lohnen , unter Hinweis darauf , dass dies nicht gleichbedeutend ist: diese eingestellt würde jzua.length als vielmehr a.length-1und erfordern würde a.splice(--j,0,a.splice(j-m[j],1)[0]))
Arnauld
Heh, ich habe auch darüber nachgedacht, aber ich dachte nicht, dass es erwähnenswert ist, weil es die gleiche Länge hat
ETHproductions
1
Easy -2:+a.splice(j-m[j--],1)
ETHproductions
2

Haskell , 85 Bytes

f x|n<-length x-1=reverse x#[n,n-1..0]
(n:r)#l=r#(take n l++drop(n+1)l)++[l!!n]
x#l=x

Probieren Sie es online! Anwendungsbeispiel: f [0,1,1,2,1,0]Erträge [4,0,2,1,3,5].

f xruft die Funktion #mit xumgekehrter Liste und einer Liste auf[length x - 1, length x - 2, ... , 0] . (n:r)#lführt die umgekehrte Einfügesortierung durch, indem rekursiv das nth-Element entfernt wird l, wobei l!!ndas nth-Element und take n l++drop(n+1)ldie Liste lmit dem entfernten nth-Element erhalten werden.

Laikoni
quelle
Haskell, so wunderschön.
FMaz
1

Perl, 61 Bytes

@o=@p=0..@ARGV-1;splice@o,$_,0,splice@o,$_-pop,1for reverse@p

Die Ausgabe endet im Array @o. Beispiel mit Eingabearray als Kommandozeilenargumente:

perl -le'@o=@p=0..@ARGV-1;splice@o,$_,0,splice@o,$_-pop,1for reverse@p;print@o' 0 1 1 2 1 0
402135
Kjetil S.
quelle
1

Ruby, 49 Bytes

->l{(w=l.size).times{l.insert(l.shift+w-=1,w)};l}

Führt die "umgekehrte Einfügung" in der Liste aus, beginnend mit der größten Nummer.

GB
quelle