Fannkuch to klasyczny program testowy . Nazwa pochodzi od niemieckiego „Pfannkuchen” - naleśników - ze względu na podobieństwo algorytmu do przerzucania stosów naleśników. Sekwencja liczb Fannkucha jest tworzona w następujący sposób:

Weź permutację {1 ..... n}, na przykład: {4,2,1,5,3}. Weź pierwszy element, tutaj 4, i odwróć kolejność pierwszych 4 elementów: {5,1,2,4,3}. Powtarzaj tę czynność, aż pierwszy element będzie miał wartość 1, więc przerzucanie niczego więcej nie zmieni: {3,4,2,1,5}, {2,4,3,1,5}, {4,2,3, 1,5}, {1,3,2,4,5}

Masz napisać program lub funkcję, która oblicza sekwencję podobną do Fannkucha dla ciągów znaków alfabetycznych. Zamiast używania liczb do wskazania, ile elementów listy należy przerzucić za każdym razem, należy użyć pozycji litery w alfabecie. Na przykład interlinia cwskazuje, że należy odwrócić kolejność pierwszych 3 elementów, a interlinia awskazuje, że sekwencja jest zakończona.

Wejście

Dane wejściowe będą dostarczane jako ciąg przez stdin lub jako argument funkcji. Ciąg będzie zawierał od 1 do 26 wyraźnych małych liter. Ciągi nie będą zawierać liter, których równoważny indeks spowodowałby, że algorytm Fannkuch przerzucił więcej elementów niż istnieje.

Wynik

Programy lub funkcje powinny zwracać lub drukować na początku sekwencji terminów utworzonych przez zastosowanie algorytmu Fannkuch aż do anapotkania wiodącego , w tym łańcucha początkowego. Na przykład, jeśli dane wejściowe to bca, możesz wydrukować:

bca
cba
abc

W wydrukowanych wynikach można zastosować dowolny rozsądny separator - przecinki, znaki nowej linii itp. Dowolny wybór białych znaków jest dopuszczalny.

Jako kolejny przykład, jeśli twoje dane wejściowe to eabdcmożesz zwrócić:

("eabdc"
 "cdbae"
 "bdcae"
 "dbcae"
 "acbde")

Zasady i punktacja

To jest golf golfowy - wygrywa najkrótszy program. Standardowe luki są niedozwolone.

Pyth, 16 bajtów

.u+_<NJhxGhN>NJz

Demonstracja.

Naprawdę przydatna jest funkcja „powtarzaj, aż przestanie się zmieniać” funkcji redukcji Pytha. Jest to używane z .ufunkcją skumulowanego zmniejszania, aby wyświetlać wszystkie wyniki. Ciało redukcji jest tak naiwne, jak to tylko możliwe, ale nie mogłem znaleźć nic lepszego.

T-SQL, 213 bajtów

Oczywiście, ponieważ SQL jest naprawdę duży, ale było to interesujące. Utworzono jako funkcję tabeli wbudowanej przy użyciu rekurencyjnego zapytania CTE.

CREATE FUNCTION F(@ CHAR(26))RETURNS TABLE RETURN WITH R AS(SELECT @ S UNION ALL SELECT CAST(STUFF(S,1,ASCII(LEFT(S,1))-96,REVERSE(LEFT(S,ASCII(LEFT(S,1))-96)))AS CHAR(26))FROM R WHERE LEFT(S,1)<>'a')SELECT*FROM R

Rozszerzony

CREATE FUNCTION F(@ CHAR(26))
RETURNS TABLE 
RETURN WITH R AS(
    SELECT @ S            -- Initial string as an anchor for the recursion
    UNION ALL 
    SELECT CAST(
        STUFF(                                    -- Stuff into 
            S,                                    -- string S
            1,                                    -- from position 1
            ASCII(LEFT(S,1))-96,                  -- to index value of first char
            REVERSE(LEFT(S,ASCII(LEFT(S,1))-96))  -- the reverse of the index first chars
            )
        AS CHAR(26))
    FROM R 
    WHERE LEFT(S,1)<>'a'  -- recurse until first char is a
)SELECT*FROM R

Używany w następujący sposób

SELECT * FROM F('eabdc')
S
--------------------------
eabdc                     
cdbae                     
bdcae                     
dbcae                     
acbde                     

(5 row(s) affected)

CJam, 22 bajty

Jest to anonimowa funkcja, która pobiera ciąg znaków na stos i zwraca listę ciągów na stosie.

{_,{_0='`-/(W%\+s_}*]}

Wypróbuj online tutaj

Python 2, 59 bajtów

def p(l):
 print l;o=ord(l[0])-97
 if o:p(l[o::-1]+l[o+1:])

Myślę, że jest to dość prosta odpowiedź. Wykorzystuje rekurencję i składnię plastra Pythona. Zadzwoń jak: p('eabdc').

SAS, 131 bajtów

sub a(s$);outargs s;put s;do while(b ne 1);b=rank(char(s,1))-96;substr(s,1,b)=reverse(substr(s,1,b));if b>1 then put s;end;endsub;

Procedura wywołania FCMP. Nongolfed poniżej (z dodatkową kontrolą gorąco polecam, ponieważ SAS ulega awarii, jeśli procedura FCMP wchodzi w nieskończoną pętlę).

options cmplib=work.funcs;
proc fcmp outlib=work.funcs.funcs;
  sub a(s$);
    outargs s;
    put s=;
    do while (b ne 1 and z<1e5);
        b=rank(char(s,1))-96;
        substr(s,1,b) = reverse(substr(s,1,b));
        if b>1 then put s=;
        z+1;
    end;
  endsub;
quit;

Haskell, 78 bajtów

f l@(h:_)|h=='a'=[l]|1<2=l:f(reverse(take d l)++drop d l)where d=fromEnum h-96

Zastosowanie: f "eabdc"-> ["eabdc","cdbae","bdcae","dbcae","acbde"].

K5, 21 bajtów

{(|v#x),(v:*x-96)_x}\

Zaoszczędzono 5 bajtów dzięki @JohnE i kolejny bajt poprzez zmianę kolejności wyrażeń.

Po raz pierwszy na ziemi myślę, że K pokonał CJam!

Wersja 27-bajtowa

(~97=*){(|v#x),(v:-96+*x)_x}\

Haskell, 68

f l@(x:_)|x<'b'=[l]|(x,y)<-splitAt(fromEnum x-96)l=l:f(reverse x++y)

Każda bardziej skomplikowana taktyka, o której myślałem, wymagała więcej bajtów.