iteración arrastrando los pies [0..n) sin matrices

Question

Yo sé de un par de rutinas que trabajar de la siguiente manera:

X _{n + 1 =} rutina (X _n, max)

Por ejemplo, algo así como un generador de LCG:

X _{n + 1} = (a * X _n + c) mod m

No hay suficiente parametrización en este generador para generar cada secuencia.

Sueño Función:

X _{n + 1} = Rutina (X _n, max, número de permutación)

Esta rutina, parametrizado por un índice en el conjunto de todos permutaciones, devolvería el siguiente número en la secuencia. La secuencia puede ser arbitrariamente grande (por lo tanto, almacenar la matriz y usar números fácticos no es práctico.

En su defecto, ¿alguien tiene punteros a funciones similares que son apátridas o tienen una cantidad constante de estado para "max" arbitrario, tales que iterarán en una lista mezclada

Answer 1

¿Es posible indexar un conjunto de permutaciones sin haber previamente computado y almacenado todo en la memoria? Intenté algo así antes y no encontré una solución - Creo que es imposible (en el sentido matemático).

Descargo de responsabilidad: Pude haber malentendido su pregunta ...

Answer 2

Desde mi respuesta a another question:

En realidad, es posible hacer esto en espacio proporcional al número de elementos seleccionados, en lugar del tamaño del conjunto que está seleccionando a partir, independientemente de qué proporción del conjunto total está seleccionando. Haces esto generando un azar permutación, a continuación, seleccionando de ella como esto:

Escoja un cifrado en bloque, tales como TEA o XTEA. Use XOR folding para reduzca el tamaño del bloque a la más pequeña potencia de dos más grande que el conjunto del que está seleccionando. Utilice la semilla aleatoria como la clave del cifrado. Para generar un elemento n en la permutación , encriptar n con el cifrado . Si el número de salida no está en su conjunto, encripte eso. Repita hasta el número está dentro del conjunto. En promedio, tendrá que hacer menos de dos encriptaciones por número generado. Esto tiene la ventaja adicional de que si su semilla es criptográficamente segura, , entonces su permutación completa.

Escribí sobre esto con mucho más detalle here.

Por supuesto, no hay garantía de que cada permutación se puede generar (y dependiendo de su tamaño de bloque y el tamaño de la clave, que puede incluso no ser posible), pero las permutaciones, usted puede obtener son altamente aleatorio (si no estuviesen 't, no sería una buena cifra), y puedes tener tantas como quieras.

Answer 3

Si quiere una función que ocupe menos espacio en la pila, debería considerar utilizar una versión iterada, en lugar de una función. También puede usar una estructura de datos como TreeMap, y almacenarla en el disco y leer según sea necesario.

X(n+1) = Routine(Xn, max, permutation number) 
for(i = n; i > 0; i--) 
{ 
    int temp = Map.lookup(i) 
    otherfun(temp,max,perm) 
} 

Answer 4

Hay n! permutaciones de n elementos. El almacenamiento de uno que esté utilizando requiere al menos log (n!)/Log (2) bits. Según la aproximación de Stirling, esto requiere aproximadamente n log (n)/log (2) bits.

Almacenar explícitamente un índice toma log (n)/log (2) bits. Almacenar todo n, como en una matriz de índices, toma n veces más, o de nuevo n log (n)/log (2). Información teóricamente, no hay mejor manera que almacenar explícitamente la permutación.

En otras palabras, el índice que pasa de qué permutación en el conjunto que desea toma el mismo espacio de almacenamiento asintótico que simplemente escribir la permutación. Si, por ejemplo, limita el índice de la permutación a valores de 32 bits, solo puede manejar permutaciones de hasta 12 elementos. Los índices de 64 bits solo le brindan hasta 20 elementos.

A medida que el índice toma el mismo espacio que la permutación que, o bien cambiar la representación de usar sólo la permutación directamente, o aceptar el desembalaje en una matriz de tamaño N.

Answer 5

código que descomprime un índice de permutación en una matriz , con una cierta asignación de índice a permutación. Hay muchos otros, pero este es conveniente.

#include <math.h> 
#include <stdio.h> 
#include <stdlib.h> 

typedef unsigned char index_t; 
typedef unsigned int permutation; 

static void permutation_to_array(index_t *indices, index_t n, permutation p) 
{ 
    index_t used = 0; 
    for (index_t i = 0; i < n; ++i) { 
     index_t left = n - i; 
     index_t digit = p % left; 
     for (index_t j = 0; j <= digit; ++j) { 
      if (used & (1 << j)) { 
       digit++; 
      } 
     } 
     used |= (1 << digit); 
     indices[i] = digit; 
     p /= left; 
    } 
} 

static void dump_array(index_t *indices, index_t n) 
{ 
    fputs("[", stdout); 
    for (index_t i = 0; i < n; ++i) { 
     printf("%d", indices[i]); 
     if (i != n - 1) { 
      fputs(", ", stdout); 
     } 
    } 
    puts("]"); 
} 

static int factorial(int n) 
{ 
    int prod = 1; 
    for (int i = 1; i <= n; ++i) { 
     prod *= i; 
    } 
    return prod; 
} 

int main(int argc, char **argv) 
{ 
    const index_t n = 4; 
    const permutation max = factorial(n); 
    index_t *indices = malloc(n * sizeof (*indices)); 
    for (permutation p = 0; p < max; ++p) { 
     permutation_to_array(indices, n, p); 
     dump_array(indices, n); 
    } 
    free(indices); 
} 

Answer 6

Código que utiliza una interfaz de iteración. La complejidad del tiempo es O (n^2). La complejidad del espacio tiene una sobrecarga de: copia de n (log n bits), una variable de iteración (log n bits), seguimiento de ni (log n bits), copia del valor actual (log n bits), copia de p (n log n bits), creación del siguiente valor (log n bits) y un conjunto de bits de valores utilizados (n bits). No puede evitar una sobrecarga de n log n bits. En el tiempo, esto también es O (n^2), para configurar los bits. Esto se puede reducir un poco, pero a costa de usar un árbol decorado para almacenar los valores utilizados.

Esto puede modificarse para utilizar enteros de precisión arbitrarios y conjuntos de bits mediante el uso de llamadas a las bibliotecas apropiadas en su lugar, y los límites anteriores comenzarán a activarse, en lugar de limitarse a N = 8, de forma portátil (una int puede ser lo mismo que un corto, y tan pequeño como 16 bits). 9! = 362880> 65536 = 2^16

#include <math.h> 
#include <stdio.h> 

typedef signed char index_t; 
typedef unsigned int permutation; 

static index_t permutation_next(index_t n, permutation p, index_t value) 
{ 
    permutation used = 0; 
    for (index_t i = 0; i < n; ++i) { 
     index_t left = n - i; 
     index_t digit = p % left; 
     p /= left; 
     for (index_t j = 0; j <= digit; ++j) { 
      if (used & (1 << j)) { 
       digit++; 
      } 
     } 
     used |= (1 << digit); 
     if (value == -1) { 
      return digit; 
     } 
     if (value == digit) { 
      value = -1; 
     } 
    } 
    /* value not found */ 
    return -1; 
} 

static void dump_permutation(index_t n, permutation p) 
{ 
    index_t value = -1; 
    fputs("[", stdout); 
    value = permutation_next(n, p, value); 
    while (value != -1) { 
     printf("%d", value); 
     value = permutation_next(n, p, value); 
     if (value != -1) { 
      fputs(", ", stdout); 
     } 
    } 
    puts("]"); 
} 

static int factorial(int n) 
{ 
    int prod = 1; 
    for (int i = 1; i <= n; ++i) { 
     prod *= i; 
    } 
    return prod; 
} 

int main(int argc, char **argv) 
{ 
    const index_t n = 4; 
    const permutation max = factorial(n); 
    for (permutation p = 0; p < max; ++p) { 
     dump_permutation(n, p); 
    } 
}