W sortowaniu naleśników jedyną dozwoloną operacją jest odwrócenie elementów jakiegoś prefiksu sekwencji. Albo pomyśl o stosie naleśników: wsuwamy gdzieś w stos szpatułkę i przewracamy wszystkie naleśniki nad szpachelką.

Na przykład sekwencję 6 5 4 1 2 3można posortować, najpierw odwracając pierwsze 6elementy (całą sekwencję), uzyskując wynik pośredni 3 2 1 4 5 6, a następnie odwracając pierwsze 3elementy, dochodząc do 1 2 3 4 5 6.

Ponieważ jest tylko jedna operacja, cały proces sortowania można opisać za pomocą sekwencji liczb całkowitych, gdzie każda liczba całkowita jest liczbą elementów / naleśników, które należy uwzględnić w odwróceniu. W powyższym przykładzie sekwencja sortowania będzie 6 3.

Kolejny przykład: 4 2 3 1można sortować za pomocą 4 2 3 2. Oto wyniki pośrednie:

         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

Zadanie:

Napisz program, który pobiera listę liczb całkowitych i drukuje prawidłową sekwencję sortowania naleśników.

Lista do sortowania może być listą oddzieloną spacjami od standardowego wejścia lub argumentami wiersza poleceń. Wydrukuj listę, jednak jest to wygodne, o ile jest w pewnym stopniu czytelne.

To jest codegolf!

Edytować:

Jak powiedziałem w komentarzach, nie musisz optymalizować wyjścia (znalezienie najkrótszej sekwencji jest trudne NP ). Jednak właśnie zdałem sobie sprawę, że tanim rozwiązaniem byłoby wyrzucanie liczb losowych, dopóki nie uzyskasz pożądanego rezultatu ([nowego?] Typu bogosortu). Żadna z dotychczasowych odpowiedzi tego nie uczyniła, więc teraz deklaruję, że twój algorytm nie powinien polegać na żadnej (pseudo) losowości .

Podczas gdy wszyscy się kopacie, oto wariant bogopancakesort w Ruby 2.0 (60 znaków), aby go wcierać:

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

GolfScript, 34/21 znaków

(Dzięki @PeterTaylor za odcięcie 4 znaków)

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

Test online

Krótsza, 21-znakowa wersja działa tylko z listami zawierającymi unikalne elementy

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

Test online

Obie wersje dają nieoptymalne rozwiązania.

Objaśnienie krótszego rozwiązania:

~]         # 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

Używa innego algorytmu niż większość innych opublikowanych. Zasadniczo chwyta najmniejszy element listy, a dwoma rzutami przesuwa go do przodu, zachowując kolejność pozostałych elementów.

Aby przesunąć n-ty element na przód:

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

Powtarza tę operację dla każdego elementu w kolejności i kończy się sortowaniem w odwrotnej kolejności. Następnie odwraca całą listę, aby pozostawić ją w pełni posortowaną.

W rzeczywistości algorytm jest odmianą 90-znakowego rozwiązania Pythona (oczywiście moje własne):

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 znaków

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

Odwróć największy naleśnik na górę, a następnie odwróć cały stos. Usuń największy naleśnik z dołu i powtórz.

ito indeks największego naleśnika. L=L[:i:-1]+L[:i]przewraca i+1naleśniki, przewraca len(L)naleśniki, a następnie upuszcza ostatni naleśnik.

Ruby 1.9 - 109 88 79 znaków

Znacznie bardziej kompaktowa wersja oparta na świetnym rozwiązaniu Pythona Keitha:

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

Orginalna wersja:

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

Jeśli nie przejmujesz się fałszywymi operacjami (odwracanie stosów wielkości 1 lub odwracanie tego samego stosu dwa razy z rzędu), możesz go nieco skrócić (96 znaków):

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

Pobiera nieposortowaną listę jako argumenty wiersza polecenia. Przykładowe użycie:

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

GolfScript, 31 29 znaków

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

Inne rozwiązanie GolfScript można również przetestować online .

Poprzednia wersja:

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

Jak to działa: przewraca największy element na górę, a następnie na ostatnie miejsce na liście. Ponieważ znajduje się teraz we właściwej pozycji, możemy go usunąć z listy.

~]         # 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 znaków

Oczekuje danych wejściowych w wierszu polecenia.

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

Rozwiązania, które drukuje, są zdecydowanie nieoptymalne. (Miałem program z dużo ładniejszym wyjściem około 24 znaków temu ....)

Logika jest dość interesująca. Zaczyna się od skatalogowania indeksu każdego elementu, gdyby był on posortowany. Następnie przechodzi przez ten katalog od prawej do lewej. Zatem zastosowanie przerzucenia polega na dostosowaniu indeksów poniżej wartości odcięcia, zamiast faktycznego przenoszenia wartości. Po kilku finaglingach udało mi się również uratować kilka postaci, wykonując jednocześnie oba obroty na iterację.

Python 2 (254)

Proste wyszukiwanie BFS, niektóre elementy są wbudowane, prawdopodobnie można by je bardziej skompresować bez zmiany stylu wyszukiwania. Mam nadzieję, że to pokazuje, jak trochę zacząć grać w golfa (zbyt wiele, by być w prostym komentarzu).

Posługiwać się:

python script.py 4 2 3 1

(2 spacje = 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

To nie jest wydajne: nie znajdzie najlepszej sekwencji sortowania, a podana sekwencja może nawet zawierać brak operacji (tj. Odwracanie tylko pierwszego elementu), niemniej jednak wynik jest prawidłowy.

Dane wyjściowe są podane w postaci:

n_1 n_2
n_3 n_4
n_5 n_6
...

Które powinny być odczytywane jako sekwencji koziołki: n_1 n_2 n_3 n_4 n_5 n_6 .... Jeśli chcesz uzyskać dane wyjściowe takie jak:

n_1 n_2 n_3 n_4 n_5 n_6 ...

Po prostu dodaj przecinek do printwyciągu.

Python - 282 znaków

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

Mój pierwszy golf golfowy; Nie mam złudzeń, że wygram , ale dobrze się bawiłem. Nadawanie wszystkim nazwom jednoznakowym sprawia, że ​​lęk jest przerażający, powiem ci! Jest to uruchamiane z wiersza poleceń, przykładowa implementacja poniżej:

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

Nie ma nic szczególnego ani pomysłowego w sposobie, w jaki to zrobiłem, ale FAQ sugeruje opublikowanie wersji bez golfa dla zainteresowanych czytelników, więc zrobiłem to poniżej:

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

Podstawowym algorytmem, który zastosowałem, jest ten wymieniony w artykule wiki, do którego link znajduje się w pytaniu :

Najprostszy algorytm sortowania naleśników wymaga co najwyżej 2n-3 przerzutów. W tym algorytmie, będącym odmianą sortowania selekcyjnego, doprowadzamy największy naleśnik, który nie został jeszcze posortowany na górę za pomocą jednego obrotu, a następnie obniżamy go do jego ostatecznej pozycji o jeszcze jedno, a następnie powtarzamy to dla pozostałych naleśników.

C # - 264 259 252 237 znaków

Wykorzystuje najprostszy algorytm i zapewnia poprawne wyjście bez zbędnych przerzutów. Mógłbym zgolić 7 znaków, jeśli pozwolę, aby zawierały 1 (non-flips) na wyjściu, ale to brzydkie.

I uciekają się do stosowania gotodla maksymalnej golfage. Zapisano także niektóre znaki, pozwalając mu wykonywać non-flipy (ale nie drukować ich).

Ostatnie ulepszenie: utrzymywanie tablicy wejściowej jako ciągów zamiast konwersji na ints.

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;}}}}}

Nie golfowany:

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;
                }
            }
        }
    }
}

Oto moje wstępne rozwiązanie, bez golfa (264 znaki w golfa):

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 bajtów

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

Wypróbuj online! Znajduje maksimum, odwraca je do tyłu i rekurencyjnie sortuje pozostałą listę.

Edycja: -1 bajt dzięki BMO

Perl 5.10 (lub wyższy), 66 bajtów

Obejmuje +3dla -n The, use 5.10.0aby doprowadzić język do poziomu perl 5.10 jest uważany za darmowy

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

Uruchom z wejściem jako jedną linię na STDIN:

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

Sortuje listę, wielokrotnie znajdując inwersję, przewracając ją do przodu, a następnie odwracając i przewracając wszystko z powrotem do swojej poprzedniej pozycji. Jest to równoważne z zamianą inwersji, więc nie muszę cofać (co jest niewygodne w przypadku łańcuchów, ponieważ odwróciłoby cyfry wartości konwertowanych np. 12Na 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--);}}}

wersja czytelna

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--);
        }
    }
}