Bonjour a vous,

je cherche a avoir un algorithme de generation de permutation aleatoire de faible complexite et empreinte memoire. Voici l'enonce du probleme

Soit N un entier naturel quelconque. Une permutation est une fonction P: [1:N] -> [1:N] tel que \forall i,j, i!=j, P(i)!=P(j). Soit R la permutation inverse defini par P(R(i)) = i.

Je cherche a une permutation non trivial tel que calculer P(i) et R(i) sont des operations qui coutent O(1). Ceci est possible en stockant explicitement les fonctions P et R. Cependant, j'ai besoin que l'algorithme n'utilise pas de memoire annexe. C'est a dire O(1). Stocker la permutation entiere couterait O(N).

J'aimerai avoir des permutation aleatoire uniformes dans l'espace des permutation (tel que generer par l'algorithme de Knuth), mais ca ne semble pas tres realiste. Je me contenterait de permutations non trivial a partir du moment ou je peu en generer beaucoup (disons au moins log(N)).

J'imagine que la cle du probleme vient de fonctions generatrices. Mais mon cours de math la dessus est trop loin pour que j'arrive a resoudre le proleme moi meme (si tout est qu'il y ait une solution).

Avez vous des idees?

Merci.

Erik

Je ne suis pas sur de comprendre pourquoi ton algorithme ne peut pas utiliser de memoire annexe. Tout programme utilise de la memoire de toute facon non ?

Par pas de memoire annexe je veux dire rien de plus que O(1). (Stocker un entier de taille N, c'est O(1) dans ma vie. Mais ca ne l'est pas dans celle de chris.)

Je ne veux pas de memoire annexe pour des raisons de performances. Si tu stocke de la memoire, disons O(N) avec l'encodage explicite de la permutation, alors l'access a ce tableau coute O(1) a chaque query de la valeur de P(i). L'algorithme qui utilise la permutation que je cherches a construire accede les P(i) dans un ordre aleatoire et non predictible. Ainsi, chaque access se passe sur une ligne de cache differente et je trash le cache de mon processeur.

Si stocker la permutation necessitait une zone memoire beaucoup plus petite (disons O(1)), alors chaque access a P(i) utiliserait le meme espace memoire de taille limite, et je ne trasherai pas mon cache.

"Je cherche a une permutation non trivial tel que calculer P(i) et R(i) sont des operations qui coutent O(1)."

Qu'entend-tu précisément par permutation non triviale

"Qu'entend-tu précisément par permutation non triviale?"

Je ne sais pas bien. Je le saurais que je verrai la tete de la permutation. Un truc du genre P(i)=i+k c'est trivial.

En pratique, je cherche a reordonner les sommets d'un graphe. L'ordre naturel "1, 2, 3, 4, ... , N" a de tres mauvaise propriete pour mon algorithme. Mais un ordre aleatoire uniforme dans l'ensemble des ordres a de bonne propriete. Tous les ordres triviaux que j'ai essaye P(i)=i+k, P(i)=N-i+k ne vont pas marcher.

J'ai envie de dire qu'une propriete du genre: "la probabilite que P(i)<P(j) pour tout i et j, i!=j est entre .3 et .7" me semble raisonnable.

J'ai pensé à ça vite fait :

1 2 3 4 5 6 7 8 9 10
1 10 2 9 3 8 4 7 5 6

P(i) = E(i / 2) + 1 si i impair
P(i) = N - E(i / 2) si i pair

Ça me semble vérifier ta propriété mais je ne sais pas si c'est satisfaisant pour ton problème.

la permutation est deterministe, donc elle ne peut pas respecter la propriete qui est stochastique
de plus, les ordres naturels sont conserver.

"la permutation est deterministe, donc elle ne peut pas respecter la propriete qui est stochastique"

J'avoue que le problème me semble très loin d'être trivial

En fait j'avais cru comprendre que tu cherchais au moins une permutation telle que pour un couple (i, j) choisi au hasard, alors P(i) < P(j) compris entre 0.3 et 0.7.

Mais là j'ai du mal à voir ce que tu veux comme permutation : tu veux une permutation non déterministe ? C'est-à-dire que pour une permutation donnée tu ne pourra pas savoir quel sera P(i) ? Comment mémoriser ça ?

"J'avoue que le problème me semble très loin d'être trivial"

Si le probleme etait trivial, je ne l'aurais pas poste ici

Je ne veux pas une permutation unique, hard coder une permutation n'est probablement pas une bonne idee, le but etant d'empecher des cas pathologique.

A P fixe, P(i)<P(j) c'est 0 ou 1. Mais la "variable aleatoire" dans l'histoire est P. Du coup P(i)<P(j) est un "evenement". je voudrais que pour tout i et pour tout j, cette probabilite ne soit pas trop proche de 1 ou de 0.

Dans les coulisses, chris m'a suggere: P(i) = a*i+b[mod N] avec gcd(a,N)=1. Il parait que ca genere des permutations ce truc la. Mais je n'ai pas encore essaye.

Si vous voulez plus de background sur ce que je fais. Voici une description plus precise de mon probleme.

Soit G=(V,E) un graphe. Soit P une permutation du graph. Soit G'=(V,A), un graph oriente tel que (u,v) \in A si et seulement si (u,v) \in E et P(u)<P(v). Soit L la longeur du plus long chemin (oriente) de G'. Probleme: trouver P qui minimise L.

Si trouver la permutation coute plus que O(1), alors j'ai une methode plus rapide pour resoudre le probleme qui necessite de trouver une permutation.

"Dans les coulisses, chris m'a suggere: P(i) = a*i+b[mod N] avec gcd(a,N)=1. Il parait que ca genere des permutations ce truc la. Mais je n'ai pas encore essaye. "

On dirait que oui, ça a l'air plutôt pas mal mais j'aimerais bien connaître la théorie qui se cache là-dessous ?

Oh... une simple association d'idée.

bijection de [1..n] dans [1..n],
bijection de [0..n-1] dans [0..n-1]
automorphisme d'un groupe fini
x -> a.x
ajoutons en plus un décalage pour mélanger un peu plus
x -> a.x + b.

Après, j'ignore ce que ça vaut d'un point de vue probabiliste, mais on a n.phi(n) permutations comme ça (où phi(.) est la fonction indicatrice d'Euler : http://fr.wikipedia.org/wiki/Indicatrice_d%27Euler ). Dans le lot, il doit bien y en avoir des potables.