algorithm - tipos - rango en excel formula

Generación de rango combinado con un PRNG en lugar de barajar

Question

¿Hay algún algoritmo conocido que pueda generar un rango combinado [0..n) en tiempo lineal y espacio constante (cuando la producción se produce iterativamente), dado un valor de inicialización arbitrario?

Supongamos que n puede ser grande, por ejemplo, en muchos millones, por lo que no se requiere un requisito para producir potencialmente cada permutación posible, sobre todo porque es inviable (el espacio de valor de la semilla debería ser enorme). Esta es también la razón para un requerimiento de espacio constante. (Por lo tanto, específicamente no estoy buscando un algoritmo de reorganización de matriz, ya que eso requiere que el rango se almacene en una matriz de longitud n, y así usaría espacio lineal).

Conozco la pregunta 162606 , pero no presenta una respuesta a esta pregunta en particular: las asignaciones de los índices de permutación a las permutaciones dadas en esa pregunta requerirían un gran valor de semilla.

Idealmente, actuaría como un LCG con un período y rango de n , pero el arte de seleccionar c para un LCG es sutil. Simplemente satisfacer las restricciones para c en un período completo de LCG puede satisfacer mis requisitos, pero me pregunto si hay alguna idea mejor.

Answer 1

Aquí hay una implementación de Python del LCG de la respuesta de FryGuy . Porque necesitaba escribirlo de todos modos y pensé que podría ser útil para otros.

import random
import math
def lcg(start, stop):
N = stop - start
# M is the next largest power of 2
M = int(math.pow(2, math.ceil(math.log(N+1, 2))))
# c is any odd number between 0 and M
c = random.randint(0, M/2 - 1) * 2 + 1
# M=2^m, so make (a-1) divisible by all prime factors and 4
a = random.randint(0, M/4 - 1) * 4 + 1
first = random.randint(0, M - 1)
x = first
while True:
x = (a * x + c) % M
if x < N:
yield start + x
if x == first:
break
if __name__ == "__main__":
for x in lcg(100, 200):
print x,

Answer 2

Basado en la respuesta de Jason , hice una implementación sencilla y directa en C #. Encuentre la siguiente potencia más grande de dos más grande que N. Esto hace que sea trivial generar a y c, ya que c necesita ser relativamente primo (lo que significa que no puede ser divisible por 2, aka impar), y (a-1) necesita ser divisible por 2, y (a-1) debe ser divisible por 4. Estadísticamente, debe tomar 1-2 congruencias para generar el próximo número (ya que 2N> = M> = N).

class Program
{
IEnumerable<int> GenerateSequence(int N)
{
Random r = new Random();
int M = NextLargestPowerOfTwo(N);
int c = r.Next(M / 2) * 2 + 1; // make c any odd number between 0 and M
int a = r.Next(M / 4) * 4 + 1; // M = 2^m, so make (a-1) divisible by all prime factors, and 4
int start = r.Next(M);
int x = start;
do
{
x = (a * x + c) % M;
if (x < N)
yield return x;
} while (x != start);
}
int NextLargestPowerOfTwo(int n)
{
n |= (n >> 1);
n |= (n >> 2);
n |= (n >> 4);
n |= (n >> 8);
n |= (n >> 16);
return (n + 1);
}
static void Main(string[] args)
{
Program p = new Program();
foreach (int n in p.GenerateSequence(1000))
{
Console.WriteLine(n);
}
Console.ReadKey();
}
}

Answer 3

Mire en Registros de cambio de retroalimentación lineal, se pueden usar para esto exactamente. La forma breve de explicarlos es que empiezas con una semilla y luego iteras usando la fórmula

x = (x << 1) | f(x)

donde f (x) solo puede devolver 0 o 1.

Si eliges una buena función f , x recorrerá todos los valores entre 1 y 2 ^ n-1 (donde n es un número), de una manera buena, pseudoaleatoria. Las funciones de ejemplo se pueden encontrar here , por ejemplo, para 63 valores que puede usar

f(x) = ((x >> 6) & 1) ^ ((x >> 5) & 1)

Answer 4

Parece que quieres un algoritmo que garantiza producir un ciclo de 0 a n-1 sin repeticiones. Es casi seguro que hay un montón de ellos dependiendo de sus requisitos; La teoría de grupos sería la rama más útil de las matemáticas si desea ahondar en la teoría detrás de ella.

Si quieres rápido y no te preocupan los patrones de predictibilidad / seguridad / estadística, un LCG es probablemente el enfoque más simple. La página de wikipedia a la que vinculó contiene este conjunto de requisitos (bastante simple):

El período de un LCG general es como mucho m, y para algunas opciones de mucho menos que eso. El LCG tendrá un período completo si y solo si:

1. c y m son relativamente primos,
2. a - 1 es divisible por todos los factores primos de m
3. a - 1 es un múltiplo de 4 si m es un múltiplo de 4

Alternativamente, puede elegir un período N> = n, donde N es el valor más pequeño que tiene propiedades numéricas convenientes, y simplemente descartar cualquier valor producido entre n y N-1. Por ejemplo, la N más baja = 2 ^k - 1> = n le permitiría usar registros de desplazamiento de realimentación lineal (LFSR). O encuentre su algoritmo criptográfico favorito (RSA, AES, DES, lo que sea) y con una clave particular, descubra el espacio N de números que permute, y para cada paso aplique el cifrado una vez.

Si n es pequeño pero desea que la seguridad sea alta, ese es probablemente el caso más complicado, ya que cualquier secuencia S probablemente tenga un período N mucho mayor que n, pero tampoco es trivial para derivar una secuencia de números no repetitiva con un período más corto. que N. (por ejemplo, si pudieras tomar la salida de S mod n y garantizar una secuencia de números no repetitiva, eso daría información sobre S que un atacante podría usar)

Answer 5

Vea mi artículo sobre permutaciones seguras con cifras de bloque para una forma de hacerlo.