Als Informatiker sind Sie wahrscheinlich alle mit den grundlegenden Listenoperationen von Pop und Push vertraut . Hierbei handelt es sich um einfache Vorgänge, mit denen eine Liste von Elementen geändert wird. Haben Sie schon einmal von dem Flop gehört ? (wie im Flip- Flop )? Es ist ziemlich einfach. Kehren Sie mit einer Zahl n die ersten n Elemente der Liste um. Hier ist ein Beispiel:

>>> a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> a.flop(4)
[4, 3, 2, 1, 5, 6, 7, 8, 9, 10]

Das Coole an der Flop-Operation ist, dass Sie damit einige coole Dinge für eine Liste tun können, wie zum Beispiel das Sortieren . Wir werden etwas Ähnliches mit Flops machen:

Eine Liste von ganzen Zahlen gegeben, "Nachbar es". Mit anderen Worten, sortieren Sie es so, dass jedes doppelte Element nacheinander angezeigt wird.

Das geht mit Flops! Nehmen Sie zum Beispiel die folgende Liste:

>>> a = [3, 2, 1, 4, 3, 3, 2]
>>> a.flop(4)
[4, 1, 2, 3, 3, 3, 2]
>>> a.flop(3)
[2, 1, 4, 3, 3, 3, 2]
>>> a.flop(6)
[3, 3, 3, 4, 1, 2, 2]

Dies führt uns zur Definition der heutigen Herausforderung:

Geben Sie bei einer gegebenen Liste von Ganzzahlen eine beliebige Menge von Flops aus, die dazu führen, dass die Liste benachbart ist.

Am Beispiel der letzten Liste sollten Sie Folgendes ausgeben:

4
3
6

weil das Floppen der Liste um 4, dann um 3 und dann um 6 eine benachbarte Liste ergibt. Denken Sie daran, dass Sie nicht die kürzestmögliche Liste der Flops drucken müssen, die einer Liste benachbart sind. Wenn Sie gedruckt hatten:

4
4
4
3
1
1
6
2
2

Stattdessen wäre dies immer noch eine gültige Ausgabe. Sie dürfen jedoch niemals eine Zahl ausgeben, die größer als die Länge der Liste ist. Dies liegt daran, dass für eine Liste das a = [1, 2, 3]Aufrufen a.flop(4)unsinnig ist.

Hier sind einige Beispiele:

#Input:
[2, 6, 0, 3, 1, 5, 5, 0, 5, 1]

#Output
[3, 7, 8, 6, 9]


#Input
[1, 2]

#Output
<any list of integers under 3, including an empty list>


#Input
[2, 6, 0, 2, 1, 4, 5, 1, 3, 2, 1, 5, 6, 4, 4, 1, 4, 6, 6, 0]

#Output
[3, 19, 17, 7, 2, 4, 11, 15, 2, 7, 13, 4, 14, 2]


#Input
[1, 1, 1, 1, 2, 2, 2, -1, 4]

#Output
[]


#Input
[4, 4, 8, 8, 15, 16, 16, 23, 23, 42, 42, 15]

#Output
[12, 7]

Beachten Sie, dass in jedem dieser Beispiele die angegebene Ausgabe nur eine mögliche gültige Ausgabe ist. Wie ich bereits sagte, ist jeder Satz von Flops, der an die angegebene Liste angrenzt, eine gültige Ausgabe . Mit diesem Python-Skript können Sie überprüfen, ob eine bestimmte Liste von Flops einer Liste korrekt benachbart ist.

Sie können Eingaben und Ausgaben in jedem vernünftigen Format vornehmen. Beispielsweise sind Funktionsargumente / Rückgabewert, STDIN / STDOUT, Lesen / Schreiben einer Datei usw. gültig. Wie üblich ist dies Code-Golf . Machen Sie also das kürzeste Programm, das Sie können, und haben Sie Spaß! :)

Haskell , 98 71 Bytes

h.r
h(x:s)|(a,b)<-span(/=x)s=l b:l s:h(b++r a)
h e=e
r=reverse
l=length

Probieren Sie es online!

Erläuterung

Für eine Liste der Länge nerzeugt diese Methode 2*nFlops. Es funktioniert, indem Sie das letzte Element der Liste betrachten, nach demselben Element in der Liste suchen und es an die vorletzte Position drehen. Dann wird die Liste mit dem zuletzt entfernten Element rekursiv "benachbart".

Für die Liste [1,2,3,1,2]funktioniert der Algorithmus wie folgt:

[1,2,3,1,2]  flip longest prefix that ends in 2: flop 2
[2,1,3,1,2]  bring first element to second to last position: flop n-1 = flop 4
[1,3,1,2,2]  recursively work on n-1 list
[1,3,1,2]    there is no other 2: flop 0
[1,3,1,2]    flop n-1 = flop 3
[1,3,1,2]    recurse
[1,3,1]      flop 1
[1,3,1]      flop 2
[3,1,1]      recurse
[3,1]        flop 0
[3,1]        flop 1
 ...

Alles in allem ergibt dies die Flops [2,4,0,3,1,2,0,1,0,0]und die Liste der Nachbarn [3,1,1,2,2].

Wolfram Language (Mathematica) , 71 Byte

If[(n=Tr[1^#])<1,{},{i=Last@Ordering@#,n,n-1,i-1}~Join~#0[#~Drop~{i}]]&

Probieren Sie es online!

Wie es funktioniert

Gibt bei gegebener Länge neine Folge von 4nFlops aus, die das Array in aufsteigender Reihenfolge sortieren: insbesondere indem doppelte Elemente nebeneinander platziert werden.

Die Idee ist, ein Array zu sortieren, indem wir sein größtes Element an das Ende verschieben und dann die ersten n-1Elemente des Arrays sortieren . Um die Implementierung der Flop-Operation zu vermeiden, verschieben wir das größte Element so ans Ende, dass die anderen Elemente nicht gestört werden:

{3, 2, 1, 5, 3, 3, 2}    starting array, with largest element in position 4
{5, 1, 2, 3, 3, 3, 2}    flop 4 to put the largest element at the beginning
{2, 3, 3, 3, 2, 1, 5}    flop 7 to put the largest element at the end
{1, 2, 3, 3, 3, 2, 5}    flop 6 (7-1) to reverse the effect of flop 7 on other elements
{3, 2, 1, 3, 3, 2, 5}    flop 3 (4-1) to reverse the effect of flop 4 on other elements

Wenn sich das größte Element in Position befindet i, ist die Sequenz der Flops, die es zum Ende bewegt, im Allgemeinen gleich i, n, n-1, i-1.

Python 2 , 69 Bytes

l=input()
while l:k=l.index(max(l));print-~k,len(l),;l=l[:k:-1]+l[:k]

Probieren Sie es online!

Jelly , 19 17 Bytes

ỤỤạ‘Ḣ
ỤÇÐƤĖµUż’ṚF

Sortiert die Liste.

Probieren Sie es online!

Sauber , 88 Bytes

Ich denke, es gibt eine möglicherweise kürzere mit Wachen, aber ich habe sie noch nicht gefunden.

import StdEnv
$[h:t]#(a,b)=span((<>)h)t
=map length[b,t]++ $(b++r a)
$e=e
r=reverse

$o r

Probieren Sie es online!

Als Funktionsliteral. Funktioniert genauso wie Laikonis Haskell-Antwort , spielt aber etwas anders und natürlich auch in einer anderen Sprache.

JavaScript, 150 Byte

(a,f=n=>(a=[...a.slice(0, n).reverse(),...a.slice(n)],n),l=a.length,i=0)=>a.reduce(c=>[...c,f(a.indexOf(Math.max(...a.slice(0, l-i)))+1),f(l-i++)],[])

Probieren Sie es online!

JavaScript, 151 Bytes

a=>{f=n=>(a=[...a.slice(0,n).reverse(),...a.slice(n)],n),r=[];for(i=a.length+1;--i>0;)r.push(f(a.indexOf(Math.max(...a.slice(0, i)))+1),f(i));return r}

Probieren Sie es online!

Beide sortieren das Array grundsätzlich, indem sie die maximale Anzahl an den Anfang und dann nach hinten drehen und dies mit dem verbleibenden Array wiederholen. Der erste benutzt reduct, der zweite eine for-Schleife.

Ungolfed:

array => {
  let flop = n => {
    array = [...array.slice(0, n).reverse(), ...array.slice(n)]; 
    return n;
  }
  let flops = [];
  for (let i = array.length + 1; --i > 0;) 
  {
    let maxIndex = array.indexOf(Math.max(...array.slice(0, i)));
    flops.push(flop(maxIndex + 1), flop(i));
  }
  return flops;
}

Perl 5.10 (oder höher), 66 Byte

Beinhaltet +3für -n Das use 5.10.0Bringen der Sprache auf Level 5.10 gilt als kostenlos

#!/usr/bin/perl -n
use 5.10.0;
$'>=$&or$.=s/(\S+) \G(\S+)/$2 $1/*say"$. 2 $."while$.++,/\S+ /g

Mit der Eingabe als eine Zeile auf STDIN ausführen:

flop.pl <<< "1 8 3 -5 6"

Sortiert die Liste, indem wiederholt eine Inversion gefunden, nach vorne geworfen, dann die Inversion geworfen und alles an seine alte Position zurückgeworfen wird.

Es war überraschend schwer, in den gleichen Ballpark wie Python zu gelangen :-)

C (gcc) , 165-160 Bytes

• Vielen Dank an ceilingcat für die Einsparung von fünf Bytes.

m,j,t;f(A,l)int*A;{for(j=0;j+j<l;A[j]=A[l+~j],A[l+~j++]=t)t=A[j];}F(A,l)int*A;{for(;l;f(A,++m),printf("%d,%d,",m,l),f(A,l--))for(j=m=0;j<l;j++)m=A[j]>A[m]?j:m;}

• Probieren Sie es online!
• Nachprüfung