Bei der Pfannkuchensortierung ist es nur zulässig, die Elemente eines Präfixes der Sequenz umzukehren. Oder stellen Sie sich einen Stapel Pfannkuchen vor: Wir legen irgendwo einen Spatel in den Stapel und drehen alle Pfannkuchen über dem Spatel um.

Zum Beispiel kann die Sequenz 6 5 4 1 2 3sortiert werden, indem zuerst die ersten 6Elemente (die gesamte Sequenz) umgedreht werden, um das Zwischenergebnis zu erhalten 3 2 1 4 5 6, und dann die ersten 3Elemente umgedreht werden, um zu gelangen 1 2 3 4 5 6.

Da es nur eine Operation gibt, kann der gesamte Sortierprozess durch eine Folge von Ganzzahlen beschrieben werden, wobei jede Ganzzahl die Anzahl der Elemente / Pfannkuchen ist, die einen Pr-Flip enthalten sollen. Für das obige Beispiel wäre die Sortierreihenfolge6 3 .

Ein weiteres Beispiel: 4 2 3 1Kann mit sortiert werden 4 2 3 2. Hier sind die Zwischenergebnisse:

         4 2 3 1
flip 4:  1 3 2 4
flip 2:  3 1 2 4
flip 3:  2 1 3 4
flip 2:  1 2 3 4

Die Aufgabe:

Schreiben Sie ein Programm, das eine Liste mit ganzen Zahlen erstellt und eine gültige Pfannkuchensortierfolge ausgibt.

Die zu sortierende Liste kann entweder eine durch Leerzeichen von stdin getrennte Liste oder Befehlszeilenargumente sein. Drucken Sie die Liste aus, aber es ist praktisch, solange sie etwas lesbar ist.

Das ist Codegolf!

Bearbeiten:

Wie ich in den Kommentaren sagte, müssen Sie die Ausgabe nicht optimieren (die kürzeste Sequenz zu finden ist NP-schwer ). Aber ich nur klar , dass eine billige Lösung wäre, Zufallszahlen zu werfen , bis Sie das gewünschte Ergebnis erhalten (a [neu?] Art von Bogosort). Keine der Antworten hat dies bisher getan, daher erkläre ich jetzt, dass Ihr Algorithmus sich nicht auf eine (Pseudo-) Zufälligkeit stützen sollte .

Hier ist eine bogopancakesort-Variante in Ruby 2.0 (60 Zeichen), um es einzureiben:

a=$*.map &:to_i
a=a[0,p(v=rand(a.size)+1)].reverse+a[v..-1]while a!=a.sort

GolfScript, 34/21 Zeichen

(Danke @PeterTaylor für das Abschneiden von 4 Zeichen)

~].{,,{1$=}$\}2*${.2$?.p)p.@\-+}/,

Online-Test

Eine kürzere Version mit 21 Zeichen funktioniert nur für Listen mit eindeutigen Elementen

~].${.2$?.p)p.@\-+}/,

Online-Test

Beide Versionen führen zu suboptimalen Lösungen.

Erklärung für die kürzere Lösung:

~]         # read input from stdin
.$         # produce a sorted copy from lowest to highest
{          # iterate over the sorted list
  .2$?     # grab the index of the element
  .p       # print the index
  )p       # increment and print the index
  .@\-+    # move the element to the front
}/
,          # leave the length of the list on the stack
           # this flips the reverse sorted list to become sorted

Dabei wird ein anderer Algorithmus verwendet als bei den meisten anderen Veröffentlichungen. Grundsätzlich wird das kleinste Element der Liste erfasst und mit zwei Umblättern nach vorne verschoben, wobei die Reihenfolge der anderen Elemente beibehalten wird.

So verschieben Sie das n-te Element nach vorne:

1 2 3 4 5 6 7   # let's move the 3rd (0-based) element to the front
# flip the first 3 elements
3 2 1 4 5 6 7
# flip the first 3+1 elements
4 1 2 3 5 6 7

Dieser Vorgang wird für jedes Element in der angegebenen Reihenfolge wiederholt. Am Ende wird eine Liste mit umgekehrten Sortierungen angezeigt. Anschließend wird die gesamte Liste umgedreht, um sie vollständig sortiert zu lassen.

Tatsächlich ist der Algorithmus eine Variation einer Python-Lösung mit 90 Zeichen (meine eigene natürlich):

d=map(int,raw_input().split());i=0
while d:n=d.index(max(d));d.pop(n);print n+i,n-~i,;i+=1

Python, 91 90 Zeichen

L=map(int,raw_input().split())
while L:i=L.index(max(L));print-~i,len(L),;L=L[:i:-1]+L[:i]

Lege den größten Pfannkuchen nach oben und drehe dann den ganzen Stapel um. Den größten Pfannkuchen vom Boden nehmen und wiederholen.

iist der Index des größten Pfannkuchens. L=L[:i:-1]+L[:i]dreht i+1Pfannkuchen um, dreht len(L)Pfannkuchen um und lässt dann den letzten Pfannkuchen fallen.

Ruby 1.9 - 109 88 79 Zeichen

Viel kompaktere Version basierend auf Keiths großartiger Python-Lösung:

a=$*.map &:to_i;$*.map{p v=a.index(a.max)+1,a.size;a=a[v..-1].reverse+a[0,v-1]}

Originalfassung:

a=$*.map &:to_i
a.size.downto(2){|l|[n=a.index(a[0,l].max)+1,l].map{|v|v>1&&n<l&&p(v);a[0,v]=a[0,v].reverse}}

Wenn Sie sich nicht für falsche Operationen interessieren (Stapel der Größe 1 umkehren oder denselben Stapel zweimal hintereinander umkehren), können Sie ihn etwas kürzer machen (96 Zeichen):

a=$*.map &:to_i
a.size.downto(2){|l|[a.index(a[0,l].max)+1,l].map{|v|p v;a[0,v]=a[0,v].reverse}}

Übernimmt die unsortierte Liste als Befehlszeilenargument. Anwendungsbeispiel:

>pc.rb 4 2 3 1
4
2
3
2

GolfScript, 31 29 Zeichen

~].${1$?).p.2$.,p>-1%\@<+)}%,

Eine weitere GolfScript-Lösung kann auch online getestet werden .

Vorherige Version:

~].$-1%{1$?).2$>-1%@2$<+.,\);}/

So funktioniert es: Es kippt den größten Eintrag nach oben und dann an die letzte Stelle in der Liste. Da es sich nun an der richtigen Position befindet, können wir es aus der Liste entfernen.

~]         # Convert STDIN (space separated numbers) to array
.$-1%      # Make a sorted copy (largest to smallest)
{          # Iterate over this copy
  1$?)     # Get index of item (i.e. largest item) in the remaining list,
           # due to ) the index starts with one
  .        # copy (i.e. index stays there for output)
  2$>      # take the rest of the list...
  -1%      # ... and reverse it 
  @2$<     # then take the beginning of the list
  +        # and join both. 
           # Note: these operations do both flips together, i.e.
           # flip the largest item to front and then reverse the complete stack
  .,       # Take the length of the list for output
  \);      # Remove last item from list
}/

Perl, 103 100 Zeichen

Erwartet Eingaben in der Befehlszeile.

for(@n=sort{$ARGV[$a]<=>$ARGV[$b]}0..$#ARGV;@n;say$i+1,$/,@n+1)
{$i=pop@n;$_=@n-$_-($_<=$i&&$i)for@n}

Die gedruckten Lösungen sind ausgesprochen suboptimal. (Ich hatte vor ungefähr 24 Zeichen ein Programm mit viel schönerer Ausgabe ....)

Die Logik ist irgendwie interessant. Zunächst wird der Index jedes Elements in sortierter Reihenfolge katalogisiert. Anschließend wird dieser Katalog von rechts nach links durchlaufen. Das Anwenden eines Flip beinhaltet also das Anpassen von Indizes unterhalb des Cutoff-Werts, anstatt die Werte tatsächlich zu verschieben. Nach einigem Hin und Her konnte ich auch ein paar Zeichen speichern, indem ich beide Flips pro Iteration gleichzeitig ausführte.

Python 2 (254)

Einfache BFS-Suche, einige Sachen sind eingebettet, könnten wahrscheinlich mehr komprimiert werden, ohne den Suchstil zu ändern. Hoffentlich zeigt dies vielleicht, wie man ein bisschen Golf spielt (zu viel, um es in einem einfachen Kommentar zu beschreiben).

Verwenden:

python script.py 4 2 3 1

(2 Leerzeichen = Tab)

import sys
t=tuple
i=t(map(int,sys.argv[1:]))
g=t(range(1,len(i)+1))
q=[i]
p={}
l={}
while q:
 c=q.pop(0)
 for m in g:
  n=c[:m][::-1]+c[m:]
  if n==g:
   s=[m]
   while c!=i:s+=[l[c]];c=p[c]
   print s[::-1]
   sys.exit()
  elif n not in p:q+=[n];p[n]=c;l[n]=m

Python2: 120

L=map(int,raw_input().split())
u=len(L)
while u:i=L.index(max(L[:u]))+1;L[:i]=L[i-1::-1];L[:u]=L[u-1::-1];print i,u;u-=1

Es ist nicht effizient: Es findet nicht die beste Sortierfolge und die angegebene Sequenz kann sogar No-Ops enthalten (dh nur das erste Element spiegeln), trotzdem ist die Ausgabe gültig.

Die Ausgabe erfolgt in der Form:

n_1 n_2
n_3 n_4
n_5 n_6
...

Welche sollte als Folge von Flips gelesen werden: n_1 n_2 n_3 n_4 n_5 n_6 .... Wenn Sie eine Ausgabe erhalten möchten, wie:

n_1 n_2 n_3 n_4 n_5 n_6 ...

Fügen Sie einfach ein Komma in die printAnweisung ein.

Python - 282 Zeichen

import sys
s=sys.argv[1]
l=s.split()
p=[]
for c in l:
 p.append(int(c))
m=sys.maxint
n=0
while(n==(len(p)-1)):
 i=x=g=0
 for c in p:
  if c>g and c<m:
   g=c
   x=i
  i+=1
 m=g
 x+=1
 t=p[:x]
 b=p[x:]
 t=t[::-1]
 p=t+b
 a=len(p)-n;
 t=p[:a]
 b=p[a:]
 t=t[::-1]
 p=t+b
 print p
 n+=1

Mein allererster Code Golf; Ich bin keine Illusionen unter werde ich gewinnen , aber ich hatte viel Spaß. Es ist erschreckend zu lesen, wenn man alle Ein-Zeichen-Namen sicher angibt. Lassen Sie es mich Ihnen sagen! Dies wird über die Befehlszeile ausgeführt (Beispielimplementierung unten):

Python PancakeSort.py "4 2 3 1"
[1, 3, 2, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]

Es gibt nichts Besonderes oder Erfinderisches an der Art und Weise, wie ich das gemacht habe, aber in den FAQ wird vorgeschlagen, eine nicht-golfende Version für interessierte Leser zu veröffentlichen.

import sys

pancakesStr = sys.argv[1]
pancakesSplit = pancakesStr.split()
pancakesAr = []
for pancake in pancakesSplit:
    pancakesAr.append(int(pancake))

smallestSorted = sys.maxint
numSorts = 0

while(numSorts < (len(pancakesAr) - 1)):
    i = 0
    biggestIndex = 0
    biggest = 0
    for pancake in pancakesAr:
        if ((pancake > biggest) and (pancake < smallestSorted)):
            biggest = pancake
            biggestIndex = i
        i += 1

    smallestSorted = biggest  #you've found the next biggest to sort; save it off.
    biggestIndex += 1   #we want the biggestIndex to be in the top list, so +1.

    top = pancakesAr[:biggestIndex]
    bottom = pancakesAr[biggestIndex:]

    top = top[::-1] #reverse top to move highest unsorted number to first position (flip 1)
    pancakesAr = top + bottom   #reconstruct stack

    alreadySortedIndex = len(pancakesAr) - numSorts;

    top = pancakesAr[:alreadySortedIndex]
    bottom = pancakesAr[alreadySortedIndex:]

    top = top[::-1] #reverse new top to move highest unsorted number to the bottom position on the unsorted list (flip 2)
    pancakesAr = top + bottom   #reconstruct list

    print pancakesAr    #print after each flip

    numSorts += 1

print "Sort completed in " + str(numSorts) + " flips. Final stack: "
print pancakesAr

Der grundlegende Algorithmus, den ich verwendet habe, ist derjenige, der in dem Wiki-Artikel erwähnt wird, der in der Frage verlinkt ist :

Der einfachste Pancake-Sortieralgorithmus erfordert höchstens 2n-3 Flips. Bei diesem Algorithmus, einer Variation der Auswahlsorte, bringen wir den größten noch nicht sortierten Pfannkuchen mit einem Schlag nach oben und bringen ihn dann mit einem weiteren in seine endgültige Position. Wiederholen Sie dies für die verbleibenden Pfannkuchen.

C # - 264 259 252 237 Zeichen

Verwendet den einfachsten Algorithmus und erzeugt eine korrekte Ausgabe ohne redundante Umkehrungen. Könnte 7 Zeichen weniger bedeuten, wenn ich zulasse, dass Einsen (Nicht-Flips) in die Ausgabe einbezogen werden, aber das ist hässlich.

Ich habe mich gotofür maximales Golfen entschieden. Außerdem wurden einige Zeichen gespeichert, indem es Nicht-Flips ausführte (aber nicht druckte).

Letzte Verbesserung: Belassen Sie das Eingabe-Array als Zeichenfolge, anstatt es in Ints umzuwandeln.

using System.Linq;class P{static void Main(string[]a){var n=a.ToList();for(int p
=n.Count;p>0;p--){int i=n.IndexOf(p+"")+1;if(i<p){f:if(i>1)System.Console.Write
(i);n=n.Take(i).Reverse().Concat(n.Skip(i)).ToList();if(i!=p){i=p;goto f;}}}}}

Ungolfed:

using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        var numbers = args.ToList();

        for (int pancake = numbers.Count; pancake > 0; pancake--)
        {
            int index = numbers.IndexOf(pancake+"") + 1;
            if (index < pancake)
            {
                flip:

                if (index > 1)
                    System.Console.Write(index);

                numbers = numbers.Take(index)
                                 .Reverse()
                                 .Concat(numbers.Skip(index))
                                 .ToList();

                if (index != pancake)
                {
                    index = pancake;
                    goto flip;
                }
            }
        }
    }
}

Hier ist meine anfängliche Lösung, ungolfed (264 Zeichen Golf):

using System.Linq;
using System;

class Program
{
    static void Main(string[] args)
    {
        var numbers = args.Select(int.Parse).ToList();

        Action<int> Flip = howMany =>
        {
            Console.Write(howMany);
            numbers = numbers.Take(howMany)
                             .Reverse()
                             .Concat(numbers.Skip(howMany))
                             .ToList();
        };

        for (int pancake = numbers.Count; pancake > 0; pancake--)
        {
            int index = numbers.IndexOf(pancake) + 1;
            if (index < pancake)
            {
                if (index > 1)
                    Flip(index);
                Flip(pancake);
            }
        }
    }
}

Haskell , 72 71 Bytes

h s|(a,x:b)<-span(<maximum s)s=map length[x:a,s]++h(reverse b++a)
h e=e

Probieren Sie es online! Findet das Maximum, dreht es nach hinten und sortiert die verbleibende Liste rekursiv.

Edit: -1 Byte dank BMO

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 Umkehrung gefunden wird, diese nach vorne gekippt wird, dann die Umkehrung gekippt wird und alles zurück in seine alte Position gekippt wird. Und das ist gleichbedeutend mit dem Vertauschen der Inversion, damit ich nicht umkehren muss (was bei Strings umständlich ist, da es die Ziffern der Werte umkehren würde, die z. B. 12in konvertieren 21).

C # - 229

using System;using System.Linq;class P{static void Main(string[] a){
var n=a.ToList();Action<int>d=z=>{Console.Write(z+" ");n.Reverse(0,z);};
int c=n.Count;foreach(var s in n.OrderBy(x=>0-int.Parse(x))){
d(n.IndexOf(s)+1);d(c--);}}}

lesbare Version

using System;
using System.Linq;
class P {
    static void Main(string[] a) {
        var n = a.ToList();
        Action<int> d = z => { Console.Write(z + " "); n.Reverse(0, z); };
        int c = n.Count;
        foreach (var s in n.OrderBy(x => 0 - int.Parse(x))) {
            d(n.IndexOf(s) + 1); d(c--);
        }
    }
}