Ayer hice esta pregunta sobre el riffle shuffles. Parece que la pregunta de ayer fue demasiado difícil, por lo que esta es una tarea relacionada pero mucho más fácil.

Hoy se le pide que determine si una permutación es en realidad una mezcla aleatoria. Nuestra definición de riffle shuffle está adaptada de nuestra última pregunta:

La primera parte del shuffle es la división. En la división se divide el mazo de cartas en dos. Las dos subsecciones deben ser continuas, mutuamente excluyentes y exhaustivas. En el mundo real, desea que su partición sea lo más parecida posible, sin embargo, en este desafío esto no es una consideración, todas las particiones, incluidas las que están degeneradas (una partición está vacía) son de igual consideración.

Después de haber sido particionadas, las tarjetas se unen de tal manera que las tarjetas mantienen su orden relativo dentro de la partición de la que son miembros . Por ejemplo, si la carta A está antes de la carta B en el mazo y las cartas A y B están en la misma partición, la carta A debe estar antes de la carta B en el resultado final, incluso si el número de cartas entre ellas ha aumentado. Si A y B están en particiones diferentes, pueden estar en cualquier orden, independientemente de su orden inicial, en el resultado final.

Cada riffle shuffle se puede ver como una permutación del mazo de cartas original. Por ejemplo la permutación

1,2,3 -> 1,3,2

es un riffle shuffle Si divides la baraja así

1, 2 | 3

vemos que cada tarjeta 1,3,2tiene el mismo orden relativo que todas las demás tarjetas de su partición. 2Todavía está después 1.

Por otro lado, la siguiente permutación no es un riffle shuffle.

1,2,3 -> 3,2,1

Podemos ver esto porque para las dos particiones (no triviales)

1, 2 | 3
1 | 2, 3 

Hay un par de cartas que no mantienen su orden relativo. En la primera partición 1y 2cambiar su orden, mientras que en la segunda partición 2y 3cambiar su orden.

Tarea

Dada una permutación a través de cualquier método razonable, determine si representa una combinación aleatoria válida. Debe generar dos valores constantes distintos, uno para "Sí, este es un aleatorio" y otro para "No, no es un aleatorio".

Este es el código de golf, por lo que las respuestas se puntuarán en bytes, siendo mejores menos bytes.

Casos de prueba

1,3,2 -> True
3,2,1 -> False
3,1,2,4 -> True
2,3,4,1 -> True
4,3,2,1 -> False
1,2,3,4,5 -> True
1,2,5,4,3 -> False
5,1,4,2,3 -> False
3,1,4,2,5 -> True
2,3,6,1,4,5 -> False

JavaScript (ES6), 47 bytes

Toma datos como una matriz de enteros. Devuelve un booleano.

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

Casos de prueba

let f =

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

;[
  [1,3,2      ],  // -> True
  [3,2,1      ],  // -> False
  [3,1,2,4    ],  // -> True
  [2,3,4,1    ],  // -> True
  [4,3,2,1    ],  // -> False
  [1,2,3,4,5  ],  // -> True
  [1,2,5,4,3  ],  // -> False
  [3,1,4,2,5  ],  // -> True
  [2,3,6,1,4,5]   // -> False
]
.forEach(a => console.log(JSON.stringify(a) + ' -> ' + f(a)))

¿Cómo?

La matriz de entrada A es una combinación aleatoria válida si consta de como máximo dos secuencias entrelazadas distintas de enteros consecutivos.

Las reglas de desafío especifican que tenemos una permutación de [1 ... N] . Por lo tanto, no es necesario que verifiquemos adicionalmente que la unión ordenada de estas secuencias realmente resulte en dicho rango.

Usamos un contador x inicializado en A [0] y un contador y inicialmente indefinido.

Para cada entrada z en A , comenzando con la segunda:

• Verificamos si z es igual a x + 1 o y + 1 . En caso afirmativo, incrementamos el contador correspondiente.
• De lo contrario: si y todavía no está definido, lo inicializamos en z .
• De lo contrario: hacemos que la prueba falle.

Haskell , 41 bytes

n%h=n+0^(n-h)^2
f l=elem(foldl(%)0$l++l)l

Pruébalo en línea!

Comprueba si la lista concatenada a sí misma contiene los números 0..n-1en orden como subsecuencia.

Haskell , 43 bytes

stoma una lista de enteros como en los ejemplos de OP y devuelve a Bool.

s p=or[f(<x)p++f(>=x)p<[1..]|x<-p]
f=filter

Pruébalo en línea!

Cómo funciona

• La comprensión de la lista prueba cada elemento xde pa su vez y comprueba si puede ser el primer elemento de la segunda partición del shuffle. Luego orregresa Truesi alguno de los cheques fueron True.
• La comprensión hace esto dividiendo (con filter) pen elementos más pequeños y más grandes que (o iguales a) x, concatenando y verificando si la lista resultante es [1..length p], es decir, los elementos en orden.
• La verificación de si la lista resultante [1..length p]se realiza al ver si el resultado es estrictamente más pequeño que la lista infinita [1..] == [1,2,3,etc.], lo que da el mismo resultado para cualquier permutación.

Jalea , 13 6 bytes

ỤIṢḊRẠ

Pruébalo en línea!

Versión alternativa, desafío de fecha posterior, 5 bytes

Ụ>ƝSỊ

Pruébalo en línea!

Cómo funciona

ỤIṢḊRẠ  Main link. Argument: A (permutation of [1, ..., n])

Ụ       Grade up; sort the indices of A by their respective values.
        For shuffles, the result is the concatenation of up to two increasing
        sequences of indices.
 I      Compute the forward differences.
        In a shuffle, only one difference may be negative.
  Ṣ     Sort the differences.
   Ḋ    Dequeue; remove the first (smallest) difference.
    R   Range; map each k to [1, ..., k].
        This yields an empty array for non-positive values of k.
     Ạ  All; check if all resulting ranges are non-empty.

Python 2 , 39 bytes

l=input()
n=0
for x in l*2:n+=n==x
l[n]

Pruébalo en línea!

Toma la lista indexada en 0 y las salidas a través del código de salida.

Brachylog , 9 bytes

o~cĊ⟨⊆⊇⟩?

Pruébalo en línea!

El predicado tiene éxito si la entrada representa un riffle shuffle y falla si no lo hace, lo que significa, entre otras cosas, que si el predicado se ejecuta como un programa completo, el éxito se imprimirá true.y el fracaso se imprimirá false.. La entrada se toma como una lista de cualquier tipo de elementos y se interpreta como una permutación de sí misma ordenada.

   Ċ         Some length-two list
 ~c          which concatenated
o            is the input sorted
    ⟨        satisfies the condition that its first element
     ⊆       is an ordered not-necessarily-contiguous sublist
        ?    of the input
      ⊇      which is an ordered superlist of
       ⟩     the list's second element.

Siento que hay algo en el espíritu ⊆ᵐque debería funcionar en lugar de la construcción de "sandwich" de cuatro bytes ⟨⊆⊇⟩.

Python 2 , 75 60 47 bytes

gracias a Dennis por -13 bytes

x={0}
for v in input():x=x-{v-1}|{v}
len(x)<3>q

Pruébalo en línea!

La salida es a través del código de salida.

Ruby , 35 bytes

->l{l.any?{|a|l&[*1..a]|l==l.sort}}

Pruébalo en línea!

¿Cómo?

• l & [*1..a] | laplica una intersección y luego una unión: primero obtenga los elementos lque son <=ay luego agregue los elementos restantes de lsin cambiar el orden. Si a es el número que estamos buscando, entonces esta operación es lo mismo que ordenar l.

Limpio , 56 55 bytes

import StdEnv
?l=any(\e=sortBy(\a b=a<e&&b>=e)l<[1..])l

Pruébalo en línea!

Pyth, 5 bytes

}SQy+

Banco de pruebas

}SQy+

    +QQ  concatenated two copies of the (implicit) input
   y     all subsequences of it
}        contain an element equaling
 SQ      the input list sorted 

Comprueba si la lista de entrada duplicada contiene una versión ordenada de sí misma como subsecuencia.

Gracias a Erik the Outgolfer por 1 byte aprovechando mejor la entrada implícita con en +QQlugar de *2Q.

Pyth , 9 bytes

!t-.+xLQS

Banco de pruebas.

Guardado 3 bytes gracias a isaacg .

Pyth , 14 bytes

}SQm.nS.Tcd2./

Pruébalo aquí! o Verificar todos los casos de prueba.

Salidas Truey Falsepara riffle-shuffle y non-riffle-shuffle respectivamente.

¿Cómo?

} SQm.nS.Tcd2./ ~ Programa completo. Lee la entrada de STDIN y las salidas a STDOUT.

            ./ ~ Devuelve todas las divisiones de la entrada en subcadenas disjuntas (partición).
   m ~ Mapa sobre lo anterior usando una variable d.
         cd2 ~ Cortar d en listas de dos elementos.
       .T ~ Transposición justificada, ignorando ausencias.
      S ~ Ordenar (lexicográficamente).
    .n ~ Aplanar en profundidad.
} ~ Compruebe si lo anterior contiene ...
 SQ ~ La entrada ordenada.

Casco , 7 bytes

±§#OoṖD

¡Banco de pruebas!

Perl, 28 bytes

Incluye +1paraa

Entrada en STDIN, 1 basado

perl -aE '$.+=$_==$.for@F,@F;say$.>@F' <<< "3 1 2 4"

Utiliza el algoritmo de xnor

C (gcc) , 61 bytes

a,b,B;f(int*A){for(a=b=B=1;*A;A++)a-*A?B*=*A>b,b=*A:++a;b=B;}

Pruébalo en línea!