Biorąc pod uwagę sekwencję liczb całkowitych lub ściślej mówiąc, permutacja 0..N przekształcenia tej sekwencji w następujący sposób:

• wyjście [x] = bieg wsteczny (wejście [wejście [x]])
• powtarzać

Na przykład: [2,1,0]staje się [0,1,2]i odwrócony jest [2,1,0]. [0,2,1]staje się [0,1,2]i odwraca [2,1,0].

Przykład 1

In:   0 1 2
S#1:  2 1 0
S#2:  2 1 0
Output: 1

Przykład 2

In:   2 1 0
S#1:  2 1 0
Output: 0

Przykład 3

In:   3 0 1 2
S#1:  1 0 3 2
S#2:  3 2 1 0
S#3:  3 2 1 0
Output: 2

Przykład 4

In:   3 0 2 1
S#1:  0 2 3 1
S#2:  2 1 3 0
S#3:  2 0 1 3
S#4:  3 0 2 1
Output: 3

Twoim zadaniem jest zdefiniowanie funkcji (lub programu), która przyjmuje permutację liczb całkowitych 0..Ni zwraca (lub generuje) liczbę kroków do momentu wystąpienia permutacji, która już wystąpiła. Jeśli Xprzekształca się w, Xwówczas wyjście powinno wynosić zero, Jeśli Xprzekształca się w Yi Ydo X(lub Y), wówczas wyjście powinno wynosić 1.

Y -> Y: 0 steps
Y -> X -> X: 1 step
Y -> X -> Y: 1 step
A -> B -> C -> D -> C: 3 steps
A -> B -> C -> D -> A: 3 steps
A -> B -> C -> A: 2 steps
A -> B -> C -> C: 2 steps
A -> B -> C -> B: also 2 steps

Przypadki testowe:

4 3 0 1 2 -> 0 3 4 1 2 -> 4 3 2 1 0 -> 4 3 2 1 0: 2 steps 
4 3 2 1 0 -> 4 3 2 1 0: 0 steps
4 3 1 2 0 -> 4 1 3 2 0 -> 4 3 2 1 0 -> 4 3 2 1 0: 2 steps
1 2 3 0 4 -> 4 1 0 3 2 -> 0 3 4 1 2 -> 4 3 2 1 0 -> 4 3 2 1 0: 3 steps
5 1 2 3 0 4 -> 0 5 3 2 1 4 -> 1 5 3 2 4 0 -> 1 4 3 2 0 5 -> 
  5 1 3 2 0 4 -> 0 5 3 2 1 4: 4 steps

Jeśli Twój język nie obsługuje „funkcji”, możesz założyć, że sekwencja jest podana jako osobna lista liczb całkowitych, takich jak 0 1 2lub 3 1 0 2w jednym wierszu.

Zabawne fakty:

• sekwencja 0,1,2,3, .., N zawsze przekształci się w N, ..., 3,2,1,0
• sekwencja N, .., 3,2,1,0 zawsze przekształci się w N, .., 3,2,1,0
• sekwencja 0,1,3,2, ..., N + 1, N zawsze przekształci się w N, ..., 3,2,1,0

Dodatkowe zadanie : Opracuj wzór matematyczny.

Zasady opcjonalne :

• Jeśli pierwszym indeksem Twojego języka jest 1 zamiast 0, możesz użyć permutacji 1..N(możesz po prostu dodać jeden do każdej liczby całkowitej w przykładzie i testach).

JavaScript (ES6), 54 bajty

a=>~(g=a=>g[a]||~-g(g[a]=a.map(i=>a[i]).reverse()))(a)

Wypróbuj online!

Python 2 , 67 bajtów

f=lambda l,*h:len(h)-1if l in h else f([l[i]for i in l][::-1],l,*h)

Wypróbuj online!

Pyth, 10 9 8 bajtów

tl.u@LN_

Wyjaśnienie:

t               One less than
 l              the number of values achieved by
  .u            repeating the following lambda N until already seen value:
    @LN_N         composing permutation N with its reverse
         Q      starting with the input.

Zestaw testowy .

Haskell, 52 bajty

([]#)
a#x|elem x a= -1|n<-x:a=1+n#reverse(map(x!!)x)

Wypróbuj online!

a # x                -- function '#' takes a list of all permutations
                     -- seen so far (-> 'a') and the current p. (-> 'x')
  | elem x a = -1    -- if x has been seen before, return -1 
  | n<-x:a =         -- else let 'n' be the new list of seen p.s and return
    1 +              -- 1 plus
       n #           -- a recursive call of '#' with the 'n' and
        reverse ...  -- the new p.

([]#)                -- start with an empty list of seen p.s 

Perl 6 , 44 35 bajtów

-9 bajtów dzięki nwellnhof

{($_,{.[[R,] |$_]}...{%.{$_}++})-2}

Wypróbuj online!

Wyjaśnienie:

{                              }  # Anonymous code block
                  ...    # Create a sequence where:
  $_,  # The first element is the input list
     {.[[R,] |$_]} # Subsequent elements are the previous element reverse indexed into itself
                     {        }    # Until
                      %.{$_}       # The index of the listt in an anonymous hash is non-zero
                            ++     # Then post increment it
 (                            )-2  # Return the length of the sequence minus 2

J, 33 27 26 bajtów

-7 dzięki bubblerowi

_1(+~:i.0:)|.@C.~^:(<@!@#)

Wypróbuj online!

w jaki sposób

oryginalne wyjaśnienie. moje ostatnie ulepszenie zmienia tylko element, który znajduje „indeks pierwszego elementu, który już widzieliśmy”. używa teraz „sita nub”, aby zrobić to w mniejszej liczbie bajtów.

1 <:@i.~ [: ({: e. }:)\ |.@C.~^:(<@!@#)
                        |.@C.~          NB. self-apply permutation and reverse
                              ^:        NB. this many times:
                                (<@!@#) NB. the box of the factorial of the
                                        NB. the list len.  this guarantees
                                        NB. we terminate, and the box means
                                        NB. we collect all the results
         [: ({: e. }:)\                 NB. apply this to those results:
                      \                 NB. for each prefix
             {: e. }:                   NB. is the last item contained in 
                                        NB. the list of previous items?
1 <:@i.~                                NB. in that result find:
1    i.~                                NB. the index of the first 1
  <:@                                   NB. and subtract 1

Zwróć uwagę, że cała ostatnia fraza 1<:@i.~[:({:e.}:)\poświęcona jest znalezieniu „indeksu pierwszego elementu, który już był widziany”. Wydaje się to okropnie długie, ale nie mogłem więcej w golfa. Sugestie mile widziane.

Galaretka , 6 bajtów

Ṛị$ƬL’

Wypróbuj online!

1-indeksowany.

Dyalog APL, 29 28 27 bajtów

¯2∘+∘≢{⍵,⍨⊂⌽(⍋⍳⊢)⊃⍵}⍣{⍺≢∪⍺}

Zajmuje tablice w pudełku. Nauczę się i wyjaśnię później.

Wypróbuj tutaj jako pakiet testowy .

Czysty , 90 bajtów

import StdEnv
$l=length(until(\[h:t]=any((==)h)t)(\[h:t]=[reverse(map((!!)h)h),h:t])[l])-2

Wypróbuj online!