Desafio:

Entrada: Uma lista de números inteiros positivos distintos no intervalo .$[1, \text{list-size}]$

Saída: Um número inteiro: a quantidade de vezes que a lista é embaralhada . Para uma lista, isso significa que a lista é dividida em duas metades, e essas metades são intercaladas (ou seja, embaralhar a lista [1,2,3,4,5,6,7,8,9,10]uma vez resultaria [1,6,2,7,3,8,4,9,5,10], portanto, para esse desafio, a entrada [1,6,2,7,3,8,4,9,5,10]resultaria 1).

Regras do desafio:

• Você pode assumir que a lista conterá apenas números inteiros positivos no intervalo $[1, \text{list-size}]$ (ou $[0, \text{list-size}-1]$ se você optar por ter listas de entrada indexadas com 0).
• Você pode supor que todas as listas de entrada sejam uma lista embaralhada válida ou uma lista classificada que não seja embaralhada (nesse caso, a saída será 0).
• Você pode assumir que a lista de entrada conterá pelo menos três valores.

Exemplo passo a passo:

Entrada: [1,3,5,7,9,2,4,6,8]

Se você embaralhar, ele se torna uma vez:, [1,5,9,4,8,3,7,2,6]porque todos os itens pares indexados a 0 são os primeiros [1, ,5, ,9, ,4, ,8]e, depois, todos os itens ímpares indexados a 0 [ ,3, ,7, ,2, ,6, ].
A lista ainda não foi encomendada, por isso continuamos:

Se você embaralhar a lista novamente: Tornar-se [1,9,8,7,6,5,4,3,2]
novamente: [1,8,6,4,2,9,7,5,3]
Então: [1,6,2,7,3,8,4,9,5]
E finalmente [1,2,3,4,5,6,7,8,9]:, que é uma lista ordenada, então terminamos de embaralhar.

Nós embaralhámos o original [1,3,5,7,9,2,4,6,8]cinco vezes para chegar [1,2,3,4,5,6,7,8,9], então a saída é 5neste caso.

Regras gerais:

• Isso é código-golfe , então a resposta mais curta em bytes vence.
  Não permita que idiomas com código de golfe o desencorajem a postar respostas com idiomas que não sejam codegolf. Tente encontrar uma resposta o mais curta possível para 'qualquer' linguagem de programação.
• As regras padrão se aplicam à sua resposta com as regras de E / S padrão , para que você possa usar STDIN / STDOUT, funções / método com os parâmetros adequados e programas completos do tipo retorno. Sua chamada.
• As brechas padrão são proibidas.
• Se possível, adicione um link com um teste para o seu código (ou seja, TIO ).
• Além disso, é altamente recomendável adicionar uma explicação para sua resposta.

Casos de teste:

Input                                                   Output

[1,2,3]                                                 0
[1,2,3,4,5]                                             0
[1,3,2]                                                 1
[1,6,2,7,3,8,4,9,5,10]                                  1
[1,3,5,7,2,4,6]                                         2
[1,8,6,4,2,9,7,5,3,10]                                  2
[1,9,8,7,6,5,4,3,2,10]                                  3
[1,5,9,4,8,3,7,2,6,10]                                  4
[1,3,5,7,9,2,4,6,8]                                     5
[1,6,11,5,10,4,9,3,8,2,7]                               6
[1,10,19,9,18,8,17,7,16,6,15,5,14,4,13,3,12,2,11,20]    10
[1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20]    17
[1,141,32,172,63,203,94,234,125,16,156,47,187,78,218,109,249,140,31,171,62,202,93,233,124,15,155,46,186,77,217,108,248,139,30,170,61,201,92,232,123,14,154,45,185,76,216,107,247,138,29,169,60,200,91,231,122,13,153,44,184,75,215,106,246,137,28,168,59,199,90,230,121,12,152,43,183,74,214,105,245,136,27,167,58,198,89,229,120,11,151,42,182,73,213,104,244,135,26,166,57,197,88,228,119,10,150,41,181,72,212,103,243,134,25,165,56,196,87,227,118,9,149,40,180,71,211,102,242,133,24,164,55,195,86,226,117,8,148,39,179,70,210,101,241,132,23,163,54,194,85,225,116,7,147,38,178,69,209,100,240,131,22,162,53,193,84,224,115,6,146,37,177,68,208,99,239,130,21,161,52,192,83,223,114,5,145,36,176,67,207,98,238,129,20,160,51,191,82,222,113,4,144,35,175,66,206,97,237,128,19,159,50,190,81,221,112,3,143,34,174,65,205,96,236,127,18,158,49,189,80,220,111,2,142,33,173,64,204,95,235,126,17,157,48,188,79,219,110,250]
                                                        45

Gelatina , 8 bytes

ŒœẎ$ƬiṢ’

Experimente online!

Quão?

ŒœẎ$ƬiṢ’ - Link: list of integers A
    Ƭ    - collect up until results are no longer unique...
   $     -   last two links as a monad:
Œœ       -     odds & evens i.e. [a,b,c,d,...] -> [[a,c,...],[b,d,...]]
  Ẏ      -     tighten                         -> [a,c,...,b,d,...]
     Ṣ   - sort A
    i    - first (1-indexed) index of sorted A in collected shuffles
      ’  - decrement

JavaScript (ES6), 44 bytes

Versão mais curta sugerida por @nwellnhof

Espera um baralho com cartões 1-indexados como entrada.

f=(a,x=1)=>a[x]-2&&1+f(a,x*2%(a.length-1|1))

Experimente online!

Dado um baralho $[c_0,\ldots,c_{L-1}]$ de comprimento $L$ , definimos:

E procuramos por $n$ tal que $c_{x_n}=2$ .

JavaScript (ES6),  57 52  50 bytes

Espera um baralho com cartões indexados 0 como entrada.

f=(a,x=1,k=a.length-1|1)=>a[1]-x%k&&1+f(a,x*-~k/2)

Experimente online!

Quão?

Como o JS não possui suporte nativo para extrair fatias de array com uma etapa personalizada, simular toda a reprodução aleatória provavelmente seria um pouco caro (mas, para ser sincero, nem tentei). No entanto, a solução também pode ser encontrada apenas olhando para a 2ª carta e o número total de cartas no baralho.

$L$$n$

$c_2$$k$

Python 2, 39 bytes

f=lambda x:x[1]-2and-~f(x[::2]+x[1::2])

Try it online!

-4 thanks to Jonathan Allan.

R, 58 55 45 bytes

a=scan();while(a[2]>2)a=matrix(a,,2,F<-F+1);F

Try it online!

Simulates the sorting process. Input is 1-indexed, returns FALSE for 0.

Perl 6 , 34 32 bytes

-2 bytes graças a Jo King

{(.[(2 X**^$_)X%$_-1+|1]...2)-1}

Experimente online!

Semelhante à abordagem de Arnauld . O índice da segunda carta após n shuffles está 2**n % kcom k definido como na resposta de Arnauld.

APL (Dyalog Unicode) , 35 26 23 22 bytes ^SBCS

{⍵≡⍳≢⍵:0⋄1+∇⍵[⍒2|⍳⍴⍵]}

Experimente online!

Graças a Adám pela ajuda, Erik, o Outgolfer por -3 e ngn por -1.

O link TIO contém dois casos de teste.

Explicação:

{⍵≡⍳≢⍵:0⋄1+∇⍵[⍒2|⍳⍴⍵]}
{⍵≡⍳≢⍵:0⋄1+∇⍵[⍒2|⍳⍴⍵]} ⍝ function takes one argument: ⍵, the array
 ⍵≡⍳≢⍵                 ⍝ if the array is sorted:
 ⍵≡⍳≢⍵                 ⍝ array = 1..length(array)
      :0               ⍝ then return 0
        ⋄              ⍝ otherwise
         1+            ⍝ increment
           ∇           ⍝ the value of the recursive call with this argument:
            ⍵[      ]  ⍝ index into the argument with these indexes:
                 ⍳⍴⍵   ⍝ - generate a range from 1 up to the size of ⍵
               2|      ⍝ - %2: generate a binary mask like [1 0 1 0 1 0]
              ⍒        ⍝ - grade (sorts but returns indexes instead of values), so we have the indexes of all the 1s first, then the 0s.

¹

Perl 6 , 36 34 32 bytes

-2 bytes graças a nwellnhof

$!={.[1]-2&&$!(.sort:{$++%2})+1}

Experimente online!

Riffle reverso aleatório, classificando pelo módulo de índice 2 até que a lista seja classificada e, em seguida, retorna o comprimento da sequência.

É engraçado, geralmente não uso a abordagem recursiva para o Perl 6, mas desta vez acabou mais curto que o original.

Explicação:

$!={.[1]-2&&$!(.sort:{$++%2})+1}
$!={                           }   # Assign the anonymous code block to $!
    .[1]-2&&                       # While the list is not sorted
            $!(             )      # Recursively call the function on
               .sort:{$++%2}       # It sorted by the parity of each index
                             +1    # And return the number of shuffles

05AB1E (herdado) , 9 bytes

[DāQ#ι˜]N

Experimente online!

Explicação

[   #  ]     # loop until
  ā          # the 1-indexed enumeration of the current list
 D Q         # equals a copy of the current list
     ι˜      # while false, uninterleave the current list and flatten
        N    # push the iteration index N as output

Java (JDK) , 59 bytes

a->{int c=0;for(;a[(1<<c)%(a.length-1|1)]>2;)c++;return c;}

Experimente online!

Funciona de maneira confiável apenas para matrizes com tamanho menor que 31 ou soluções com menos de 31 iterações. Para uma solução mais geral, consulte a seguinte solução com 63 bytes:

a->{int i=1,c=0;for(;a[i]>2;c++)i=i*2%(a.length-1|1);return c;}

Experimente online!

Explicação

Em um riffle, a próxima posição é a anterior, multiplicando dois módulos por comprimento, se for ímpar ou por comprimento - 1 se for par.

Então, eu estou iterando sobre todos os índices usando essa fórmula até encontrar o valor 2 na matriz.

Créditos

• -8 bytes graças a Kevin Cruijssen . (Algoritmo anterior, usando matriz)
• -5 bytes graças a Arnauld .

J , 28 26 bytes

-2 bytes graças a Jonah!

 1#@}.(\:2|#\)^:(2<1{])^:a:

Experimente online!

Inspirado seja a solução APL da Ven.

Explicação:

               ^:       ^:a:   while 
                 (2<1{])       the 1-st (zero-indexed) element is greater than 2   
     (        )                do the following and keep the intermediate results
          i.@#                 make a list form 0 to len-1
        2|                     find modulo 2 of each element
      /:                       sort the argument according the list of 0's and 1's
1  }.                          drop the first row of the result
 #@                            and take the length (how many rows -> steps)     

K (ngn / k) , 25 bytes

Obrigado a ngn pelo conselho e pelo seu intérprete K!

{#1_{~2=x@1}{x@<2!!#x}\x}

Experimente online!

APL (NARS), caracteres 49, bytes 98

{0{∧/¯1↓⍵≤1⌽⍵:⍺⋄(⍺+1)∇⍵[d],⍵[i∼d←↑¨i⊂⍨2∣i←⍳≢⍵]}⍵}

por que usar no loop mais profundo, um algo que deve ser nlog (n), quando podemos usar um n linear? apenas por mais alguns bytes? [⍵≡⍵ [⍋⍵] O (nlog n) e o confronto de cada elemento para ver estão em ordem usando o teste ∧ / ¯1 ↓ ⍵≤1⌽⍵ O (n)]:

  f←{0{∧/¯1↓⍵≤1⌽⍵:⍺⋄(⍺+1)∇⍵[d],⍵[i∼d←↑¨i⊂⍨2∣i←⍳≢⍵]}⍵}
  f ,1
0
  f 1 2 3
0
  f 1,9,8,7,6,5,4,3,2,10
3
  f 1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20
17

Ruby , 42 bytes

f=->d,r=1{d[r]<3?0:1+f[d,r*2%(1|~-d.max)]}

Experimente online!

Quão:

Procure o número 2 dentro da matriz: se estiver na segunda posição, o baralho não foi embaralhado; caso contrário, verifique as posições em que os embaralhamento sucessivos o colocariam.

R , 70 72 bytes

x=scan();i=0;while(any(x>sort(x))){x=c(x[y<-seq(x)%%2>0],x[!y]);i=i+1};i

Experimente online!

Agora lida com o estojo zero zero.

C (GCC) 64 63 bytes

-1 byte de nwellnhof

i,r;f(c,v)int*v;{for(i=r=1;v[i]>2;++r)i=i*2%(c-1|1);return~-r;}

Essa é uma resposta drasticamente mais curta, com base nas respostas de Arnauld e Olivier Grégoire. Deixarei minha solução antiga abaixo, pois resolve o problema um pouco mais geral de decks com cartões que não são contíguos.

Experimente online

C (GCC) 162 bytes

a[999],b[999],i,r,o;f(c,v)int*v;{for(r=0;o=1;++r){for(i=c;i--;(i&1?b:a)[i/2]=v[i])o=(v[i]>v[i-1]|!i)&o;if(o)return r;for(i+=o=c+1;i--;)v[i]=i<o/2?a[i]:b[i-o/2];}}

Experimente online

a[999],b[999],i,r,o; //pre-declare variables
f(c,v)int*v;{ //argument list
    for(r=0;o=1;++r){ //major loop, reset o (ordered) to true at beginning, increment number of shuffles at end
        for(i=c;i--;(i&1?b:a)[i/2]=v[i]) //loop through v, split into halves a/b as we go
            o=(v[i]>v[i-1]|!i)&o; //if out of order set o (ordered) to false
        if(o) //if ordered
            return r; //return number of shuffles
        //note that i==-1 at this point
        for(i+=o=c+1;i--;)//set i=c and o=c+1, loop through v
            v[i]=i<o/2?a[i]:b[i-o/2];//set first half of v to a, second half to b
    }
}

R, 85 bytes

s=scan();u=sort(s);k=0;while(any(u[seq(s)]!=s)){k=k+1;u=as.vector(t(matrix(u,,2)))};k

Experimente online.

Explicação

Método estúpido (força bruta), muito menos elegante do que seguir o cartão # 2.

Em vez de embaralhar a entrada s, começamos com um vetor classificado uque embaralhamos progressivamente até que seja idêntico as . Isso fornece avisos (mas as contagens aleatórias ainda estão corretas) para comprimentos ímpares de entrada devido à dobragem de um vetor de comprimento ímpar em uma matriz de 2 colunas; nesse caso, em R, o ponto de dados ausentes é preenchido pela reciclagem do primeiro elemento de entrada.

O loop nunca terminará se fornecermos um vetor que não possa ser embaralhado.

Adendo: você salva um byte se não embaralhar. Ao contrário da resposta acima, não há necessidade de transpor com t(), no entanto, a ordem byrow=TRUEé por isso que Taparece matrix().

R , 84 bytes

s=scan();u=sort(s);k=0;while(any(s[seq(u)]!=u)){k=k+1;s=as.vector(matrix(s,,2,T))};k

Experimente online!

PowerShell , 116 114 108 84 78 bytes

-24 bytes graças a Erik a Outgolfer 's solução .

-6 bytes graças ao mazzy .

param($a)for(;$a[1]-2){$n++;$t=@{};$a|%{$t[$j++%2]+=,$_};$a=$t.0+$t.1;$j=0}+$n

Experimente online!

Wolfram Language (Mathematica) , 62 bytes

c=0;While[Sort[a]!=a,a=a[[1;;-1;;2]]~Join~a[[2;;-1;;2]];c++];c

Experimente online!

Explicação

A lista de entrada é a. Ele não é distribuído e comparado com a lista classificada até que correspondam.

Vermelho , 87 79 78 bytes

func[b][c: 0 while[b/2 > 2][c: c + 1 b: append extract b 2 extract next b 2]c]

Experimente online!

Perl 5 -pa , 77 bytes

map{push@{$_%2},$_}0..$#F;$_=0;++$_,@s=sort{$a-$b}@F=@F[@0,@1]while"@F"ne"@s"

Experimente online!

Pitão , 18 bytes

L?SIb0hys%L2>Bb1
y

Experimente online!

-2 graças a @Erik the Outgolfer.

O script possui duas linhas: a primeira define uma função y, a segunda linha chama ycom o Qargumento implícito (stdin avaliado).

L?SIb0hys%L2>Bb1
L                function y(b)
 ?               if...
  SIb            the Invariant b == sort(b) holds
     0           return 0
      h          otherwise increment...
       y         ...the return of a recursive call with:
             B   the current argument "bifurcated", an array of:
              b   - the original argument
            >  1  - same with the head popped off
          L      map...
         % 2     ...take only every 2nd value in each array
        s         and concat them back together

¹

PowerShell , 62 71 70 66 bytes

+9 bytes quando Casos de teste com um número par de elementos adicionados.

-1 byte com splatting.

-4 bytes: agrupe a expressão com $i, $jpara um novo escopo.

for($a=$args;$a[1]-2;$a=&{($a|?{++$j%2})+($a|?{$i++%2})}){$n++}+$n

Experimente online!

Japonês , 13 11 10 bytes

Levando meu intérprete brilhante, novo e muito em andamento para um test drive.

ÅÎÍ©ÒßUñÏu

Experimente ou execute todos os casos de teste

ÅÎÍ©ÒßUñÏu     :Implicit input of integer array U
Å              :Slice the first element off U
 Î             :Get the first element
  Í            :Subtract from 2
   ©           :Logical AND with
    Ò          :  Negation of bitwise NOT of
     ß         :  A recursive call to the programme with input
      Uñ       :    U sorted
        Ï      :    By 0-based indices
         u     :    Modulo 2

Python 3, 40 bytes

f=lambda x:x[1]-2and 1+f(x[::2]+x[1::2])  # 1-based
f=lambda x:x[1]-1and 1+f(x[::2]+x[1::2])  # 0-based

Experimente online!

Preciso atualizar a página com mais frequência: perdi a edição do Erik the Outgolfer fazendo um truque semelhante =)