Na classificação de panquecas, a única operação permitida é reverter os elementos de algum prefixo da sequência. Ou pense em uma pilha de panquecas: inserimos uma espátula em algum lugar da pilha e viramos todas as panquecas acima da espátula.

Por exemplo, a sequência 6 5 4 1 2 3pode ser classificada primeiro invertendo os primeiros 6elementos (a sequência inteira), produzindo o resultado intermediário 3 2 1 4 5 6e, em seguida, invertendo os primeiros 3elementos, chegando a 1 2 3 4 5 6.

Como existe apenas uma operação, todo o processo de classificação pode ser descrito por uma sequência de números inteiros, em que cada número inteiro é o número de elementos / panquecas para incluir o pr flip. Para o exemplo acima, a sequência de classificação seria 6 3.

Outro exemplo: 4 2 3 1pode ser classificado com 4 2 3 2. Aqui estão os resultados intermediários:

         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

A tarefa:

Escreva um programa que pegue uma lista de números inteiros e imprima uma sequência de classificação de panqueca válida.

A lista a ser classificada pode ser uma lista separada por espaço de stdin ou argumentos de linha de comando. Imprima a lista no entanto, é conveniente, desde que seja um pouco legível.

Isso é codegolf!

Editar:

Como eu disse nos comentários, você não precisa otimizar a saída (encontrar a sequência mais curta é difícil para o NP ). No entanto , acabei de perceber que uma solução barata seria lançar números aleatórios até obter o resultado desejado (um [novo?] Tipo de bogosort). Nenhuma das respostas até agora o fez, então declaro que seu algoritmo não deve se basear em nenhuma (pseudo-) aleatoriedade .

Enquanto todos se divertem, aqui está uma variante bogopancakesort no Ruby 2.0 (60 caracteres), para esfregar:

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

GolfScript, 34/21 caracteres

(Obrigado @ PeterTaylor por cortar 4 caracteres)

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

Teste online

Uma versão menor, com 21 caracteres, funciona apenas para listas com itens exclusivos

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

Teste online

Ambas as versões produzem soluções abaixo do ideal.

Explicação para a solução mais curta:

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

Isso usa um algoritmo diferente para a maioria dos outros postados. Basicamente, ele pega o menor elemento da lista e, com dois movimentos, move-o para a frente, preservando a ordem dos outros elementos.

Para mover o enésimo elemento para a frente:

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

Ele repete esta operação para cada elemento em ordem e termina com uma lista classificada inversa. Em seguida, vira a lista inteira para deixá-la totalmente classificada.

De fato, o algoritmo é uma variação de uma solução Python de 90 caracteres (a minha, é claro):

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 caracteres

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

Vire a maior panqueca para o topo e depois vire a pilha inteira. Retire a maior panqueca do fundo e repita.

ié o índice da maior panqueca. L=L[:i:-1]+L[:i]vira i+1panquecas, vira len(L)panquecas e depois derruba a última panqueca.

Ruby 1.9 - 109 88 79 caracteres

Versão muito mais compacta baseada na ótima solução python de Keith:

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

Versão original:

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

Se você não se importa com operações espúrias (inverter pilhas do tamanho 1 ou inverter a mesma pilha duas vezes seguidas), você pode torná-la um pouco menor (96 caracteres):

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

Toma a lista não classificada como argumentos da linha de comando. Exemplo de uso:

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

GolfScript, 31 29 caracteres

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

Outra solução GolfScript também pode ser testada online .

Versão anterior:

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

Como funciona: vira o maior item para o topo e depois para o último lugar na lista. Como agora está na posição correta, podemos removê-lo da lista.

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

Espera entrada na linha de comando.

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

As soluções que imprime são decididamente abaixo do ideal. (Eu tinha um programa com uma saída muito melhor, há cerca de 24 caracteres ....)

A lógica é meio interessante. Começa catalogando o índice de cada item, se estivesse em ordem classificada. Em seguida, itera através deste catálogo da direita para a esquerda. Portanto, aplicar um flip envolve o ajuste de índices abaixo do valor de corte, em vez de realmente mover os valores. Após algumas finalizações, eu também consegui salvar alguns caracteres fazendo os dois movimentos por iteração simultaneamente.

Python 2 (254)

A pesquisa BFS simples, algumas coisas estão embutidas, provavelmente poderia ser mais compactada sem alterar o estilo de pesquisa. Espero que isso mostre talvez como começar a jogar um pouco (demais para ser um simples comentário).

Usar:

python script.py 4 2 3 1

(2 espaços = tabulação)

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

Não é eficiente: ele não encontrará a melhor sequência de classificação, e a sequência fornecida pode até conter no-ops (ou seja, inverter apenas o primeiro elemento), no entanto, a saída é válida.

A saída é fornecida no formato:

n_1 n_2
n_3 n_4
n_5 n_6
...

Que deve ser lido como a sequência de inversões: n_1 n_2 n_3 n_4 n_5 n_6 ... . Se você deseja obter uma saída como:

n_1 n_2 n_3 n_4 n_5 n_6 ...

Basta adicionar uma vírgula na printdeclaração.

Python - 282 caracteres

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

Meu primeiro código de golfe; Não tenho ilusões de que vou ganhar , mas me diverti muito. Dar a todos os nomes de um personagem com certeza torna assustador ler, deixe-me dizer! Isso é executado na linha de comando, exemplo de implementação abaixo:

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

Não há nada de especial ou inventivo na maneira como eu lutei com isso, mas as perguntas frequentes sugerem a publicação de uma versão sem golf para os leitores interessados, então fiz isso abaixo:

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

O algoritmo básico que usei é o mencionado no artigo wiki vinculado na pergunta :

O algoritmo mais simples de classificação de panquecas requer no máximo 2n-3 movimentos. Nesse algoritmo, uma variação da classificação, levamos a maior panqueca ainda não classificada ao topo com um giro e, em seguida, levamos à sua posição final com mais uma, depois repetimos isso para as restantes panquecas.

C # - 264 259 252 237 caracteres

Usa o algoritmo mais simples e produz saída correta sem inversões redundantes. Poderia raspar 7 caracteres se eu permitisse incluir 1 (não flips) na saída, mas isso é feio.

Eu recorri ao uso goto para o máximo de golfe. Também salvou alguns caracteres, permitindo a execução de não flips (mas não os imprime).

Melhoria mais recente: manter a matriz de entrada como seqüências de caracteres em vez de converter em 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;}}}}}

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

Aqui está a minha solução inicial, sem uso de golfe (264 caracteres jogados):

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

Experimente online! Encontra o máximo, vira-o para trás e classifica recursivamente a lista restante.

Edit: -1 byte graças ao BMO

Perl 5.10 (ou superior), 66 bytes

Inclui +3para -n o use 5.10.0trazer a linguagem para nível perl 5.10 é considerado livre

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

Execute com a entrada como uma linha no STDIN:

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

Classifica a lista localizando repetidamente qualquer inversão, invertendo-a para a frente e depois invertendo e invertendo tudo de volta à sua antiga posição. E isso é equivalente a trocar a inversão, então eu não preciso inverter (o que é estranho nas strings, pois inverte os dígitos dos valores que convertem, por exemplo, 12em 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--);}}}

versão legível

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