Itère brassé [0..n) sans tableaux

Question

Je connais quelques routines qui fonctionnent comme suit:

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

Par exemple, quelque chose comme un générateur de LCG:

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

Il n'y a pas assez de paramétrage dans ce générateur pour générer chaque séquence.

rêve Fonction:

X _{n + 1} = Routine (X _n, max, nombre permutation)

Cette routine, paramétrée par un indice dans l'ensemble de tous permutations, retournerait le numéro suivant dans la séquence. La séquence peut être arbitrairement grande (donc stocker le tableau et utiliser des nombres factoradiques est impossible.)

A défaut, quelqu'un at-il des pointeurs vers des fonctions similaires qui sont sans état ou ont une quantité constante d'état pour arbitraire 'max', comme

Answer 1

Est-il possible d'indexer un ensemble de permutations sans avoir préalablement calculé et stocké le tout en mémoire? J'ai déjà essayé quelque chose comme ça et je n'ai pas trouvé de solution - je pense que c'est impossible (au sens mathématique)

Avis de non-responsabilité: J'ai peut-être mal compris votre question ...

Answer 2

De ma réponse à another question:

Il est en fait possible de le faire dans l'espace proportionnel au nombre d'éléments sélectionnés , plutôt que la taille de l'ensemble vous choisissez de, quel que soit de quelle proportion du jeu total que vous sélectionnez. Vous faites en générant une permutation aléatoire, puis en sélectionnant de celui-ci comme ceci:

Choisissez un chiffrement par bloc, comme TEA ou XTEA. Utilisez XOR folding à réduisez la taille du bloc à la plus petite puissance de deux plus grande que l'ensemble que vous sélectionnez. Utilisez la graine aléatoire comme clé du chiffrement. Pour générer un élément n dans la permutation , crypter n avec le chiffre . Si le numéro de sortie n'est pas votre ensemble, cryptez-le. Répétez jusqu'à le nombre est à l'intérieur de l'ensemble. Sur moyenne, vous devrez faire moins de deux cryptages par numéro généré. Cela a l'avantage supplémentaire que si votre graine est cryptographiquement sécurisé, est donc votre permutation entière. J'ai écrit à ce sujet de manière beaucoup plus détaillée here.

Bien sûr, il n'y a aucune garantie que chaque permutation peut être générée (et en fonction de votre taille de bloc et clé, qui peut ne pas être encore possible), mais les permutations vous pouvez obtenir sont très aléatoires (si elles weren ce ne serait pas un bon chiffre), et vous pouvez en avoir autant que vous voulez.

Answer 3

Si vous voulez une fonction qui occupe moins d'espace de pile, vous devriez envisager d'utiliser une version itérée plutôt qu'une fonction. Vous pouvez également utiliser une structure de données telle qu'une TreeMap et la stocker sur le disque, et la lire au besoin.

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

Il ya n! permutations de n éléments. Stocker celui que vous utilisez nécessite au moins les bits log (n!)/Log (2). Par approximation de Stirling, cela prend environ n bits de log (n)/log (2).

L'enregistrement explicite d'un index prend des bits log (n)/log (2). Stocker tout n, comme dans un tableau d'indices prend n fois autant, ou encore n log (n)/log (2). D'un point de vue théorique, il n'y a pas de meilleur moyen que de stocker explicitement la permutation. En d'autres termes, l'indice que vous transmettez de la permutation dans l'ensemble que vous voulez prend le même espace de stockage asymptotique que l'écriture de la permutation. Si, par exemple, vous limitez l'index de la permutation à des valeurs de 32 bits, vous ne pouvez gérer que les permutations de 12 éléments maximum. Les indices 64 bits ne vous permettent d'obtenir que 20 éléments.

Comme l'indice prend le même espace que la permutation serait, soit changer votre représentation juste utiliser la permutation directement ou accepter de déballer dans un tableau de taille N.

Answer 5

Code

qui décompresse un indice de permutation dans un tableau , avec un certain mapping de l'index à la permutation. Il y en a plein d'autres, mais celui-ci est pratique.

#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

Code qui utilise une interface itérée. La complexité du temps est O (n^2), La complexité de l'espace a une surcharge de: copie de n (log n bits), une variable d'itération (log n bits), suivi de ni (log n bits), copie de la valeur courante (log n bits), copie de p (n log n bits), création de la valeur suivante (log n bits), et un ensemble de bits de valeurs utilisées (n bits). Vous ne pouvez pas éviter une surcharge de n log n bits. Timewise, c'est aussi O (n^2), pour régler les bits. Cela peut être réduit un peu, mais au prix d'utiliser un arbre décoré pour stocker les valeurs utilisées. Cela peut être modifié pour utiliser des entiers de précision arbitraires et des ensembles de bits en utilisant des appels aux bibliothèques appropriées, et les limites ci-dessus commenceront réellement à entrer, plutôt que d'être plafonnées à N = 8, de façon portable (un int être le même qu'un court, et aussi petit que 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); 
    } 
}