Las siguientes dos preguntas son equivalentes:
"Puede que las cartas plegarse a ponerlos en orden creciente, cuando están etiquetados en un determinado orden arbitrario?"
"Puede que las cartas plegarse a producir un determinado orden arbitrario, cuando están etiquetados en orden creciente?"
El resultado relevante fue demostrado por Koehler en 1968 ("el Plegamiento de una Tira de Sellos"):
Una $n$-permutación $p$ es un plegamiento si y sólo si la orden circular
$p(i) < p(j) < p(i + 1) < p(j + 1)$
no se produce cuando se $i$ $j$ son ambos pares o ambos inclusive. Por orden circular se entiende cualquier permutación circular de las desigualdades anteriores.
E. g., su $5,3,2,1,4$ está decidido a ser un plegamiento de $1,2,3,4,5$ mediante la comprobación de que ninguno de sus permutaciones circulares contienen una larga de la forma $i,j,i+1,j+1$ $i$ $j$ de la misma paridad. Por otro lado, $5,3,2,4,1$ es no un plegamiento porque tiene la permutación circular $1,5,3,2,4$, que contiene la larga prohibido $1,3,2,4$ ($i=1,j=3$).
En la web, búsqueda "el plegamiento de la etiqueta sellos" para un montón de fuentes en línea.
He aquí un esbozo de un unoptimized algoritmo basado directamente en el resultado anterior:
def forbidden(n):
# returns a list of all "forbidden" pairs; i.e., (i,j) such that
# 1 ≤ i ≤ n-1, 1 ≤ j ≤ n-1, i ≠ j, i ≡ j (mod 2)
def is_subseq(x,y):
# returns True if x is a subsequence of y, else returns False
def is_folding(x):
# returns True if sequence x is a folding, else returns False
# cyc_perms is a list of all cyclic permutations of sequence x
for cyc_perm in cyc_perms:
for (i,j) in forbidden(len(x)):
if is_subseq([i,j,i+1,j+1],cyc_perm): return False
return True
Como un cheque en el algoritmo de corrección, he programado esta en Python y utiliza para reproducir los valores correctos de la serie de plegamientos como una función de la $N$ ( $N \le 10$ , debido a las limitaciones de tiempo).
