Алфавитный Фаннкух

14

Fannkuch - это классическая тестовая программа. Название происходит от немецкого "Pfannkuchen" - блины - для алгоритма, похожего на переворачивание стопок блинов. Последовательность чисел Фаннуча формируется следующим образом:

Возьмем перестановку {1 ..... n}, например: {4,2,1,5,3}. Возьмите первый элемент, здесь 4, и измените порядок первых 4 элементов: {5,1,2,4,3}. Повторяйте это до тех пор, пока первый элемент не станет 1, поэтому переворачивание больше ничего не изменит: {3,4,2,1,5}, {2,4,3,1,5}, {4,2,3, 1,5}, {1,3,2,4,5}

Вы должны написать программу или функцию, которая вычисляет последовательность, похожую на Фаннуч, для строк буквенных символов. Вместо того, чтобы использовать числа, чтобы указать, сколько элементов списка нужно перевернуть каждый раз, следует использовать положение буквы в алфавите. Например, ведущий cбудет означать, что вы должны изменить порядок первых 3 элементов, в то время как ведущий aуказывает, что последовательность завершена.

вход

Ввод будет предоставлен в виде строки через стандартный ввод или в качестве аргумента функции. Строка будет содержать от 1 до 26 различных строчных букв. Строки не будут содержать букв, чей эквивалентный индекс приведет к тому, что алгоритм Fannkuch перевернет больше элементов, чем существует.

Выход

Программы или функции должны возвращать или печатать, чтобы выводить последовательность терминов, полученных с помощью алгоритма Фаннуча, до тех пор, пока aне встретится ведущий , включая начальную строку. Например, если введено bca, вы можете напечатать:

bca
cba
abc

В распечатанных результатах могут использоваться любые разумные разделители - запятые, переводы строк и т. Д. Любой выбор пробела является приемлемым.

В качестве другого примера, если вы введете это, eabdcвы можете вернуть:

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

Правила и оценки

Это - выигрывает самая короткая программа. Стандартные лазейки запрещены.

Johne
источник

Ответы:

11

Pyth, 16 байт

.u+_<NJhxGhN>NJz

Демонстрация.

Функция «повторять до тех пор, пока она не перестанет изменяться» в функциях редукции Pyth очень удобна. Это используется вместе .uс функцией кумулятивного уменьшения для вывода всех результатов. Тело снижения настолько наивно, насколько это возможно, но я не мог найти ничего лучше.

isaacg
источник
5

T-SQL, 213 байт

Конечно, будучи SQL, он действительно большой, но это было интересно сделать. Создана как встроенная табличная функция с использованием рекурсивного запроса 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

расширенный

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

Используется следующим образом

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

(5 row(s) affected)
MickyT
источник
3

Python 2, 59 байт

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

Я думаю, это довольно простой ответ. Использует рекурсию и синтаксис фрагмента Python. Звоните , как: p('eabdc').

mathmandan
источник
3

SAS, 131 байт

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;

Процедура вызова FCMP. Ниже приведено (с дополнительной проверкой, которую я настоятельно рекомендую, так как SAS аварийно завершает работу, если подпрограмма FCMP входит в бесконечный цикл).


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;
Джо
источник
Хорошо сделано. У нас здесь не так много proc fcmp.
Алекс А.
2

Haskell, 78 байт

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

Использование: f "eabdc"-> ["eabdc","cdbae","bdcae","dbcae","acbde"].

Ними
источник
рассмотрите возможность использования splitAt- вы можете уменьшить его до 71 байта!
MtnViewMark
@MtnViewMark хорошо, похоже, у меня точно такой же алгоритм, до 68 байтов
гордый haskeller
2

К5, 21 байт

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

Сохранено 5 байтов благодаря @JohnE и еще один байт путем перестановки выражения.

Впервые на земле, я думаю, K победил CJam!

27-байтовая версия

(~97=*){(|v#x),(v:-96+*x)_x}\
kirbyfan64sos
источник
Вы можете сделать это немного короче, если вы используете форму «сканирования» с фиксированной запятой.
JohnE
@JohnE Спасибо! Я не осознавал, что, когда первая буква - это a, строка не изменится.
kirbyfan64sos
0

Хаскелл, 68

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

Любая более сложная тактика, о которой я думал, занимала больше байтов.

гордый хаскеллер
источник