Reordenación de secuencias

Question

Estoy tratando de estudiar la reordenación de las secuencias. Estoy teniendo dificultades para encontrar algún artículo erudito, probablemente porque no conozco las palabras clave para buscar. Espero que si describo lo que quiero hacer alguien pueda ampliar mis conocimientos o nombrar lo que estoy haciendo para poder investigarlo yo mismo.

Quiero definir una reordenación de una secuencia de forma que se pueda codificar fácilmente. Para ello utilizaré $S(...)$ .

Empiezo con la secuencia de números enteros más sencilla.

$1,2,3,4,5,...$

Tal vez quiera intercambiar pares de ellos para convertirse:

$2,1,4,3,6,5,... = S(3,-1)$ lo que significa saltar hacia adelante 3, luego saltar hacia atrás 1 y repetir.

o trillizos inversos

$3,2,1,6,5,4,9,... = S(5,-1,-1)$ lo que significa saltar hacia adelante 4, luego saltar hacia atrás 1, y una vez más hacia atrás 1 y repetir.

o algo más complicado como

$5,4,2,3,1,10,9,7,8,6,15... = S(9,-1,-2,1,-2)$

así que defino una función $S(...)$ que puede hacer eso que toma como parámetros la secuencia de pasos de la secuencia original para hacer la nueva (no lo he explicado muy bien pero tened paciencia).

Ahora claramente puedo codificar S sin dificultad, sólo necesito retener el suficiente historial de la secuencia entrante para saltar hacia atrás y hacia adelante según las indicaciones.

¿Existe un nombre para esta función? $S$ ¿o algo similar? ¿Hay alguna manera de examinar los parámetros de S para determinar si la secuencia resultante:

1. emite toda la secuencia original
2. no emite duplicados

Por ejemplo, $S(2,-1)$ produciría la secuencia $2,1,3,2,4,3,...$ que no es aceptable porque 2 se repite. Y $S(2)$ generaría $2,4,6,8,...$ que se salta algunos y tampoco es aceptable.

¿Existe una forma de generar estos ordenamientos? Está claro que hay una forma nula $S(1)$ que podría considerarse el primero.

Añadido

Este proceso consiste en manipular una secuencia infinita aplicando $S$ repetidamente. Los dos requisitos se aplican a toda la secuencia infinita generada. Así, por ejemplo $S(24,-23)$ no es válido porque eventualmente surgirá un duplicado aunque la primera iteración no lo haga.

Answer 1

Dado $S(a_1,\ldots,a_n)$ podemos determinar si genera todos los enteros a partir de $s$ verificando $\displaystyle \sum_{k=1}^n a_k = n$ y que $\displaystyle f(i) = \sum_{k=1}^i a_k$ se encarga de todos los residuos $\bmod n$ exactamente una vez.

Efectivamente, $S(a_1,\ldots,a_n)$ es la primera diferencia de $(f(0), f(1), \ldots,f(n))$ . Por ejemplo, para $S(3, -1)$ tenemos $(0, 3, 2)$ . En este formato el primer entero es siempre $0$ y el último entero es siempre $n$ .

Ahora, para generarlas, primero elegimos un $n$ . Digamos que $n = 5$ . Entonces podemos elegir una permutación arbitraria de los residuos $\mod 5$ con la condición de que el primer elemento sea $0$ y luego añadir $5$ como último elemento:

$$(0,4,1,2,3,5)$$

Como sólo se deben mantener los residuos, también podemos añadir múltiplos de $n$ :

$$(0,4,26,2,3,5)$$

Ahora bien, si codificamos en delta esta lista, tenemos un $S$ :

$$(0,4,26,2,3,5) \rightarrow S(4,22,-24,1,2)$$