¿Se puede deshacer la matriz?

15

Antecedentes

Los manejadores de cartas muy hábiles son capaces de una técnica mediante la cual cortan un mazo perfectamente por la mitad y luego intercalan perfectamente las cartas. Si comienzan con un mazo ordenado y realizan esta técnica sin fallas 52 veces seguidas, el mazo se restaurará al orden ordenado. Su desafío es tomar una baraja de cartas y una matriz de enteros y determinar si se puede ordenar usando solo barajas de Faro.

Definición

Matemáticamente, un Faro shuffle es una permutación en 2 n elementos (para cualquier número entero positivo n ) que lleva al elemento en la posición i (indexado 1) a la posición 2 i (mod 2 n +1). También nos gustaría poder manejar listas de longitud impar, así que en ese caso, solo agregue un elemento al final de la lista (un Joker, si tiene uno a mano) y Faro baraja la nueva lista como se indicó anteriormente, pero ignore el elemento ficticio agregado al verificar el orden de la lista.

Objetivo

Escriba un programa o función que tome una lista de enteros y devuelva o genere una verdad si algún número de barajas de Faro ocasionaría que esa lista se clasifique en un orden no descendente (incluso si ese número es cero; las listas pequeñas deberían dar una verdad). De lo contrario, devuelve o genera una falsedad.

Ejemplos

[1,1,2,3,5,8,13,21]  => True
[5,1,8,1,13,2,21,3] => True
[9,36,5,34,2,10,1] => True
[1,0] => True
[0] => True
[] => True
[3,2,1] => True
[3,1,2] => False
[9,8,7,6,5,4,3,2,1,0] => True
[9,8,7,6,5,4,3,2,0,1] => False
[3,1,4,1,5,9,2,6,9] => False
[-1,-1,-1,-2] => True

Puntuación

Este es el código de golf, por lo que la fuente más corta en bytes gana.

code-golf array-manipulation permutations quintapia
fuente
Para evitar confusiones con cualquier otro manejador de tarjetas, debe tenerse en cuenta que hay dos tipos de barajado de Faro. Un shuffle y un shuffle . El método descrito aquí es una combinación aleatoria. Curiosamente, solo se necesitan 8 combinaciones para devolver un mazo a su orden original. Más información
BrainSteel
¿No es esto simplemente "mezclar N + 1 veces y ver si alguna de las listas en el camino está ordenada"?
lirtosiast
En realidad, n veces es suficiente, porque hacerlo 2n veces está garantizado para encontrar todas las permutaciones posibles, pero obtendrá al menos uno de orden ascendente o descendente en el primer n.
quintopia 12/12/2015
1
Relacionado. Relacionado.
Martin Ender
1
¿El primer elemento no permanece siempre en la primera posición?
Eumel

Respuestas:

3

Pyth - 26 25 24 bytes

Utiliza una reducción acumulativa para aplicar Faro shuffle varias veces y mantener todos los resultados. Luego, lo mapea y verifica si son invariables en la clasificación, luego usa la suma para verificar si alguno es verdadero. Devuelve un positivo o cero.

smSI-db.usC_c2NQsC.tc2Qb

Test Suite .

Maltysen
fuente
3

MATL , 41 bytes

itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx

La salida es 1o 0.

Explicación

i              % get input array
tn2\           % is size odd?
?              % if that's the case
  YNh          % concat NaN at the end
]              % end if
tn             % get size of input array
t1+:           % vector 1:n+1, where n is input size, so loop will be entered even with []
"              % for loop
  x[]2e!PY)    % delete result from previous iteration and do the shuffling
  ttZN~)       % remove NaN, if there's any
  tS=A         % check if array is sorted
  t.           % copy the result. If true, break loop
]              % end for
wx             % remove unwanted intermediate result

Ejemplo

>> matl itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx
> [1,1,2,3,5,8,13,21]
1
Luis Mendo
fuente