A matriz pode ser embaralhada?

15

fundo

Manipuladores de cartas muito hábeis são capazes de uma técnica pela qual cortam um baralho perfeitamente ao meio e depois intercalam perfeitamente os cartões. Se eles começarem com um deck classificado e executarem essa técnica sem falhas 52 vezes seguidas, o deck será restaurado na ordem classificada. Seu desafio é pegar um baralho de cartas em uma matriz inteira e determinar se ele pode ser classificado usando apenas shuffles de Faro.

Definição

Matematicamente, um shuffle de Faro é uma permutação em 2 n elementos (para qualquer número inteiro positivo n ) que leva o elemento na posição i (indexada 1) para a posição 2 i (mod 2 n +1). Também gostaríamos de poder lidar com listas de tamanhos ímpares, portanto, nesse caso, basta adicionar um elemento ao final da lista (um Coringa, se você tiver uma disponível) e Faro embaralhar a nova lista como acima, mas ignore o elemento fictício adicionado ao verificar a ordem da lista.

Objetivo

Escreva um programa ou função que pegue uma lista de números inteiros e retorne ou produza uma verdade se algum número de embarques de Faro fizer com que a lista seja classificada em ordem não descendente (mesmo que esse número seja zero - listas pequenas devem dar uma verdade). Caso contrário, retorne ou produza um falso.

Exemplos

[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

Pontuação

Este é o código-golfe, e a fonte mais curta em bytes vence.

code-golf array-manipulation permutations quintopia
fonte
Para evitar confusão com qualquer outro manipulador de cartões, deve-se notar que existem dois tipos de embaralhamentos de Faro. Uma entrada aleatória e uma saída aleatória . O método descrito aqui é uma reprodução aleatória. Curiosamente, são necessários apenas oito shuffles para retornar o baralho à sua ordem original. Mais informações
BrainSteel 12/12
Isso não é apenas "N + 1 aleatoriamente e ver se alguma das listas ao longo do caminho está classificada"?
lirtosiast
Na verdade, n vezes é suficiente, porque fazê-lo 2n vezes é garantido para encontrar todas as permutações possíveis, mas você obterá pelo menos uma ordem crescente ou decrescente no primeiro n.
quintopia 12/12
1
Relacionado. Relacionado.
Martin Ender
1
o primeiro elemento não fica sempre na primeira posição?
Eumel

Respostas:

3

Pitão - 26 25 24 bytes

Utiliza redução cumulativa para aplicar o shuffle de Faro várias vezes e manter todos os resultados. Em seguida, ele mapeia através dele e verifica se eles são invariantes na classificação e, em seguida, usa sum para verificar se são verdadeiros. Retorna um positivo ou zero.

smSI-db.usC_c2NQsC.tc2Qb

Conjunto de Teste .

Maltysen
fonte
3

MATL , 41 bytes

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

A saída é 1ou 0.

Explicação

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

Exemplo

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