Añado un par de sugerencias para romper el hielo. Se dividen en dos grupos. Una se basa en la idea de seguir con los LFSR, pero modificándolos de forma diferente. El otro consiste en utilizar polinomios de permutación modular. Como esto último es nuevo en el concurso, también comento algunos trucos de implementación que pueden ayudar o no.
LFSR (mutados):
Las derivaciones en un LFSR de longitud máxima (de $n$ bits) garantizado para recorrer las combinaciones de bits de $1$ a $2^n-1$ sin repeticiones están determinados por los llamados polinomios primitivos $p(x)$ de grado $n$ en el ring $\mathbb{F}_2[x]$ . Para un $n$ hay $$ N_n=\frac1n\phi(2^n-1) $$ polinomios distintos. Aquí $\phi$ es la función totiente de Euler. Por ejemplo, cuando $n=12$ tenemos $$ 2^{12}-1=4095=3^2\cdot5\cdot7\cdot13, $$ por lo que hay $$ N_{12}=\frac1{12}(3-1)\cdot3\cdot(5-1)\cdot(7-1)\cdot(13-1)=144 $$ diferentes juegos de grifos que puede utilizar aquí. Probablemente esto no sea suficiente para ti, pero si usted está interesado puedo describir más detalles sobre cómo encontrarlos.
Dado que el LFSR produce todos los vectores distintos de cero de $n$ bits en secuencia que puede producir más variedad aplicando un mapeo biyectivo $f:\{0,1\}^n\to\{0,1\}^n$ a todas las salidas (descartando aún las salidas fuera de rango). Sería relativamente sencillo utilizar cualquier cartografía lineal no singular como $f$ : puede especificar las imágenes $f(000\ldots001)$ , $f(000\ldots010)$ , $f(000\ldots100)$ , $\ldots$ , $f(100\ldots000)$ y si son un conjunto linealmente independiente, se garantiza obtener una permutación de los vectores distintos de cero. Calculando el valor de $f(k)$ para algún vector de bits $k$ equivale a tomar el XOR bit a bit de las imágenes de los bits que son EN en $k$ . Como subconjunto muy simple de tales funciones $f$ puede utilizar una permutación aleatoria del $n$ bits. Hay $n!$ formas de permutar todas las salidas del LFSR elegido, que puede ser un número suficientemente grande para ti. Un posible inconveniente de ceñirse a permutaciones de bits es que una permutación no cambiará el peso de un vector binario.
Un inconveniente de todos los esquemas basados en LFSR es que el número $2^n-1$ puede ser bastante mayor que la longitud de tu array (en el peor de los casos casi el doble). Esto significa que la mitad de las veces descartarás la siguiente entrada. La otra clase de funciones que discuto es mejor en ese sentido.
Polinomios modulares de permutación:
Aquí es más sencillo indexar tu array como el rango $0,1,\ldots,\ell-1$ . Voy a trabajar en el anillo de la clase de residuos $R=\mathbb{Z}/L\mathbb{Z}$ de enteros módulo $L$ donde $L$ es un número entero que debe ser $\ge$ que la longitud de su matriz. Podemos tener $L=\ell$ pero necesito poner algunos requisitos a $L$ Así que quiero un poco de libertad aquí. De todos modos, sugiero el uso de mapeos polinómicos $p:R\to R$ . Aquí $p(x)$ es un polinomio en $x$ con coeficiente en $R$ (o simplemente números enteros). Hay resultados de la teoría elemental de números que nos dicen, cuando tal polinomio da lugar a una permutación de los elementos de $R$ .
El caso más sencillo es el de los polinomios lineales (todos los cálculos se realizan en módulo $L$ ) $$ p(x)=ax+b. $$ Se trata de una permutación, si y sólo si $\gcd(a,L)=1$ . No hay requisitos sobre $b$ puede ser cualquier cosa en el rango $0\le b<L$ . En total hay $L\phi(L)$ tales permutaciones. Implementar una función de este tipo es muy rápido. Basta con seleccionar una $b$ set $p(0)=b$ y a partir de ahí utilizar la fórmula $$ p(x+1)=p(x)+a,$$ o, si prefiere el pseudocódigo $$p(x+1)=(p(x)+a)\bmod L. $$ Así, utilizando un polinomio lineal modular, partirá de un punto aleatorio y utilizará una longitud de salto fija (coprima a la longitud de la matriz para garantizar que visitará todas las entradas sin repeticiones). Como has expresado tu deseo de evitar algunas correlaciones, puede que ésta no sea una buena opción.
Un polinomio un poco más aleatorio sería cuadrático. Así que echemos un vistazo a los polinomios de la forma $$ p(x)=ax^2+bx+c. $$ No es difícil demostrar que se trata de una permutación de $R$ si (se trata de un "si y sólo si" a casi todos los efectos prácticos) se cumplen los dos requisitos siguientes:
- $\gcd(b,L)=1$ y
- el coeficiente $a$ debe ser divisible por todos los números primos $p$ que son factores de $L$ .
El segundo requisito nos impone una seria restricción, ya que queremos utilizar un $a$ (por lo que no hay múltiplo de $L$ lo hará). Para que esto sea posible, necesitamos $L$ sea divisible por un cuadrado de algún primo. E incluso entonces seguimos teniendo relativamente pocas opciones. El mejor caso puede ser seleccionar $L$ para ser un cuadrado en sí, cuando podemos dejar que $a$ sea cualquier múltiplo de $\sqrt{L}$ (si $L$ es divisible por una cuarta potencia, entonces tenemos aún más espacio para jugar). Si $\ell\approx10000$ entonces el número de entradas "ficticias" podría llegar hasta $200$ . Sigue siendo mejor que con los LFSR en el peor de los casos. Otra posibilidad sería seleccionar $L$ que sea múltiplo de $2^6=64$ . Si $L=2^6M$ podemos utilizar $a=kM$ para cualquier $k$ tal que $1\le k<64$ . El número de opciones para el coeficiente $a$ es $\sqrt{L}$ en el primer caso y $63$ en el segundo.
Implementar un polinomio cuadrático también es fácil. Tenemos $p(0)=c$ , $p(1)=a+b+c$ (de nuevo modulo $L$ ). Además de $p(x)$ utilicemos la diferencia $$\Delta(x):=p(x+1)-p(x).$$ Así que sabemos que $\Delta(0)=p(1)-p(0)=a+b$ . En general, podemos calcular que $$ \Delta(x+1)-\Delta(x)=p(x+2)-2p(x+1)+p(x)=\cdots=2a. $$ Por lo tanto, si inicializa $p(0)=c$ , $\Delta(0)=a+b$ y actualizar estos dos números según las reglas $$ p(x+1)=(p(x)+\Delta(x))\bmod L $$ et $$ \Delta(x+1)=(\Delta(x)+2a)\bmod L, $$ sólo necesitas asignar memoria para dos enteros para reproducir la permutación completa.
La regla de actualización de $\Delta$ nos dice que con un polinomio de permutación cuadrático las longitudes de los saltos varían según la elección de $a$ . El número de longitudes de salto diferentes será $L/\gcd(2a,L)$ por lo que en los dos casos de ejemplo $\sqrt{L}/2$ (resp. $32$ ). Un poco mejor que con polinomios lineales, pero no estoy seguro de que sea lo suficientemente bueno para acabar con las correlaciones que quieres evitar.
