Un resultado de orden de lista interesante basado en índices de omisión por valor introducido

Question

Esto es algo muy interesante que he encontrado al intentar shuffle $n$ valores en una lista es una manera determinista destinado a buscar "random-ish". La idea es que se puede ordenar un número de valores de $r$ de $0...n-1$ en una lista empezando con un valor del índice $i=0$, a continuación, calcular el índice para el nuevo elemento en el que se inserta utilizando la fórmula de $i_1 = (i_0 + r)\mod n$. Lo que me he encontrado es que en la mayoría de los casos, hay varias colisiones, donde un número se coloca sobre otro , excepto cuando se $n = 2^k, k\in Z$.

Me escribió un programa en Python para hacer esto y mostrar el resultado.

>>> for n in range(5,11):
    print('_____')
    num_list = ['' for i in range(n)]
    i = 0
    for r in range(n):
        i = (i + r) % n
        num_list[i] += str(r) + ','
    for x in range(n):
        print(str(x)+'|'+num_list[x])


_____
0|0,4,
1|1,3,
2|
3|2,
4|
_____
0|0,3,
1|1,
2|
3|2,5,
4|4,
5|
_____
0|0,6,
1|1,5,
2|
3|2,4,
4|
5|
6|3,
_____
0|0,
1|1,
2|4,
3|2,
4|7,
5|6,
6|3,
7|5,
_____
0|0,8,
1|1,4,7,
2|
3|2,6,
4|
5|
6|3,5,
7|
8|
_____
0|0,4,
1|1,6,
2|
3|2,
4|
5|5,9,
6|3,8,
7|
8|7,
9|
>>> 

Como se puede ver, varios números se asignan el mismo valor para todos los casos, excepto donde n es una potencia de 2. ¿Alguien puede explicar esto?

Answer 1

En otras palabras, hay $n$ cubos $B_0, \ldots, B_{n - 1}$ y tiramos $r$ en un balde $B_{0 + 1 + \ldots + r\pmod{n}}$. Entonces la pregunta es para qué $n$ todos los cubos que contiene exactamente un elemento. Esto es cierto si y sólo si $0 + 1 + \ldots + r\pmod{n}$, $r = 0, \ldots, n - 1$ son todos diferentes. A su vez, este último es verdadera si y sólo si para todos los $r_1, r_2\in\{0, 1, \ldots, n - 1\}$, $r_1 < r_2$ sostiene que $(0 + 1 + \ldots + r_2) - (0 + 1 + \ldots + r_1)$ no es divisible por $n$. Y voy a demostrar que, efectivamente, esto es cierto si y sólo si $n$ es una potencia de $2$.

Re-escribir $(0 + 1 + \ldots + r_2) - (0 + 1 + \ldots + r_1)$ como sigue: $$(0 + 1 + \ldots + r_2) - (0 + 1 + \ldots + r_1) = \frac{r_2(r_2 + 1)}{2} - \frac{r_1(r_1 + 1)}{2} = \frac{(r_2 - r_1) (r_2 + r_1 + 1)}{2}.$$ Primero, considere el caso de $n = 2^k$. Asumir que la última expresión es divisible por $n = 2^k$. Esto significa que $(r_2 - r_1)(r_2 + r_1 + 1)$ es divisble por $2^{k + 1} = 2n$. Tenga en cuenta que $(r_2 - r_1)$ e $(r_2 + r_1 + 1)$ tienen distinta paridad. Esto significa que uno de estos dos números es divisible por $2n$. Tanto si estos números son positivos. Por lo tanto el número debe ser de al menos $2n$. Esto es imposible, ya que $r_1, r_2 \le n - 1$.

Ahora considere el caso de $n = 2^k \cdot u$ para algunos $k\ge 0$ y de alguna extraña $u \ge 3$. Conjunto \begin{align*} r_1 &= \begin{cases} \frac{2^{k + 1} - u - 1}{2} & \mbox{ if } u < 2^{k + 1}, \\ \frac{u - 2^{k + 1} - 1}{2} & \mbox{ if } u > 2^{k + 1},\end{casos} \\ r_2 &= \frac{2^{k + 1} + u - 1}{2}. \end{align*} Usted ve que hay dos subcases, $u < 2^{k + 1}$ e $u > 2^{k + 1}$ (la igualdad es imposible, porque la $u$ es impar). En el primer caso tenemos a$r_2 - r_1 = u$ e $(r_2 + r_1 + 1) = 2^{k + 1}$. En el segundo caso tenemos a$r_2 - r_1 = 2^{k + 1}$ e $r_1 + r_2 + 1 = u$. En cualquier caso obtenemos $$\frac{(r_2 - r_1) (r_2 + r_1 + 1)}{2} = 2^k\cdot u = n,$$ lo que significa que $(0 + 1 + \ldots + r_1) \equiv (0 + 1 + \ldots + r_2)\pmod{n}$. También debemos comprobar que $r_1, r_2\in\{0, 1, \ldots, n - 1\}$ e $r_1 < r_2$. Todo esto es obvio, con una excepción: no está claro por qué $r_2 \le n - 1$. En realidad, es el único lugar donde usamos el hecho de que $n$ no es una potencia de $2$. Así que nuestro objetivo es comprobar que $$\frac{2^{k + 1} + u - 1}{2} \le n - 1 = 2^k \cdot u - 1.$$ Esto es equivalente a la siguiente: $$2^{k + 1} + u \le 2^{k + 1} \cdot u - 1 = 2^k\cdot u + 2^k \cdot u - 1. $$ Entonces, ¿por qué es esto cierto? Debido a $u\le 2^k \cdot u$ e $2^{k + 1} = 2\cdot 2^k < u \cdot 2^k$ (esto último es debido al hecho de que $u\ge 3$)