Construction d'une bijection de [0..n] vers [0..n]

[ogaland]

Bonjour,

J'ai le problème suivant dans le cadre d'un programme informatique :

Je désire tester un programme avec en entrée un entier sur un intervalle [0..n] , mais pas de facon séquentielle. Idéalement de facon "la plus aléatoire" possible en apparence, et qui ne sortira pas deux fois le même numéro (donc il deviens invalide a l'index n+1, ou éventuellement est cyclique de période n+1)

J'ai donc essayé de trouver un moyen de créer une bijection de [0..n] vers [0..n] qui répond a cela. Et je m'apercois que ca n'a pas l'air simple ... car les contraintes informatiques me brident (en pratique je vais travailler sur de très grand nombres (128 bits et plus)).

- L'identité ou une symétrie (j = n-i) sont donc exclues (pas assez "aléatoires")
- Je ne peux pas passer directement par un générateur pseudo-aléatoire (a cause du risque de tirer deux fois le même numéro)
- Je ne peux pas faire un système ou je stocke les numéros non tirés et retire celui que j'ai tiré aléatoirement (a cause de l'occupation mémoire qui sera hors de portée)

Le mieux que j'ai réussi a faire c'est de travailler sur Z/nZ avec un nombre premier p > n, je multiplie p par mon index et je fais le modulo n, ca me garanti que tant que je n'ai pas tiré plus de n+1 numéros, je n'aurai pas de doublon. Ce système ne consomme pas de mémoire et est rapide a calculer, mais le résultat n'est pas assez "aléatoire" a mon gout, même si c'est un début.

Il y a donc un problème mathématique avec des contraintes dues a l'implémentation dans un programme informatique (mémoire limité et calcul rapide préférable).

Avez vous des pistes que je pourrai explorer (idées, travaux, lectures) ?

Merci de votre lecture.

[GaBuZoMeu]

Bonjour,

Le mieux que j'ai réussi a faire c'est de travailler sur Z/nZ avec un nombre premier p > n, je multiplie p par mon index et je fais le modulo n, ca me garanti que tant que je n'ai pas tiré plus de n+1 numéros, je n'aurai pas de doublon.

Non, ça ne garantit pas : essaie pour n = 16 et p = 19.

[lyceen95]

Une méthode simple :
Tu as ta liste d'entiers :
1
2
3...
n

Tu crées un tableau, et en face de chaque entier, tu mets un réel aléatoire (entre 0 et 1 par exemple)
1 0.1234
2 0.8453
3 0.7762
...
n 0.5675

Tu tries sur cette nouvelle colonne :
1 0.1234
n 0.5675
3 0.7762
2 0.8453

Et tu as ainsi ta liste de tous les entiers, remis dans un ordre aléatoire.

[ogaland]

Bonjour,

Le mieux que j'ai réussi a faire c'est de travailler sur Z/nZ avec un nombre premier p > n, je multiplie p par mon index et je fais le modulo n, ca me garanti que tant que je n'ai pas tiré plus de n+1 numéros, je n'aurai pas de doublon.

Non, ça ne garantit pas : essaie pour n = 16 et p = 19.

Bonjour,

Ca a l'air de marcher pour n=16 et p=19, j'ai testé ce programme python. Mes souvenirs de math sont vieux, mais je crois que ca marche quand n et p sont premiers entre eux (donc si p est premier supérieur a n).

n=16
p=19
idx = [i for i in range(n)]
fidx = [i*p % n for i in range(n)]
print("I : "+str(idx))
print("F(I) : "+str(fidx))
fidx.sort()
print("SORTED : "+str(fidx))

Il me donne :

I : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
F(I) : [0, 3, 6, 9, 12, 15, 2, 5, 8, 11, 14, 1, 4, 7, 10, 13]
SORTED : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

[ogaland]

Une méthode simple :
Tu as ta liste d'entiers :
1
2
3...
n

Tu crées un tableau, et en face de chaque entier, tu mets un réel aléatoire (entre 0 et 1 par exemple)
1 0.1234
2 0.8453
3 0.7762
...
n 0.5675

Tu tries sur cette nouvelle colonne :
1 0.1234
n 0.5675
3 0.7762
2 0.8453

Et tu as ainsi ta liste de tous les entiers, remis dans un ordre aléatoire.

Bonjour,

Oui, mais le problème de cette approche (qui répond a tous les pb sauf un) c'est que je suis obligé de garder toute la liste de nombres aléatoire en mémoire pour la trier, ce qui est impossible en pratique, je vais travailler sur des listes de 100 milliard de nombre environ (voire plus si j'arrive a bien optimiser le code). Ca donnerai une occupation mémoire en centaines de gigaoctets (largement au dessus de ma machine). Et il faut rajouter le temps processeur passé a trier.

[EDIT] Mais en y pensant, je pourrai diviser mes intervalles en intervalles plus petit, mes 100 milliards en 100 000 intervalles de 1 million et appliquer cette méthode en deux passe, une passe "aléatoire" pour choisir le million de nombre a tester, et une passe encore "aléatoire" pour passer ce million de nombre (consécutifs) en revue. Ce n'est pas tout a fait l'idéal mais c'est a creuser.

[GaBuZoMeu]

Excuse-moi, je pensais à (multiplier par modulo à chaque fois.

C'est aussi une possibilité qui vaudrait peut-être la peine d'être explorée.

Exemple pour n=17, et p=5, en partant de 3 : 3, 15, 7, 1, 5, 8, 6, 13, 14, 2,10, 16, 12, 9, 11, 4 (et on revient à 3)

[fatal_error]

hello,

je connais pas trop mais si ça peut aider, il y a les LCG ou les mlcg façon gbzm https://igm.univ-mlv.fr/~vnozick/teachi ... random.pdf

[ogaland]

Excuse-moi, je pensais à (multiplier par modulo à chaque fois.

C'est aussi une possibilité qui vaudrait peut-être la peine d'être explorée.

Exemple pour n=17, et p=5, en partant de 3 : 3, 15, 7, 1, 5, 8, 6, 13, 14, 2,10, 16, 12, 9, 11, 4 (et on revient à 3)

Ca a l'air pas mal avec cette fonction, le résultat est bien plus "aléatoire", je n'y avais pas pensé merci, je remarque juste que le 0 n'est pas dans l'ensemble d'arrivé et que le 3 se répète (si on prends autant d'éléments que le cardinal de l'ensemble de départ), ca peut se résoudre en remplacant un des 3 par 0 pour mes besoins.

Ce genre de fonction a une littérature ou des articles associés ? J'ai l'intuition qu'il faut que n soit premier pour que ca marche, mais pas de certitude

En faisant des tests j'ai aussi l'impression que la fonction i -> i^p (p premier) a du potentiel.

J'ai ces résultats avec n=17 sur les 3 fonctions qui retiennent mon attention :
f : i -> p.i % n (p = 19, premier supérieur a n)
g : i -> i^p % n (p = 5, aucune idée des conditions, j'ai l'impression que p premier suffit)
h : i -> 3.p^i % n (ton example, p = 5 (premier différent de n ?) avec 3 élement de [1,n] pour générateur)

I : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
F(I) : [0, 2, 4, 6, 8, 10, 12, 14, 16, 1, 3, 5, 7, 9, 11, 13, 15]
G(I) : [0, 1, 15, 5, 4, 14, 7, 11, 9, 8, 6, 10, 3, 13, 12, 2, 16]
H(I) : [3, 15, 7, 1, 5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3]

F ma fonction initiale est pas vraiment "aléatoire" mais mélange un peu les i (p=19 est un mauvais choix 19 % 17 = 2)
G est plus joli mais je ne sais pas encore si c'est utilisable
H ton exemple aussi très joli, mais a légèrement travailler avec un cas particulier dans le code (3 en double, un a remplacer par 0)

Merci

[ogaland]

hello,

je connais pas trop mais si ça peut aider, il y a les LCG ou les mlcg façon gbzm https://igm.univ-mlv.fr/~vnozick/teachi ... random.pdf

Hello,

Merci pour la documentation, je vais la lire pour voir si ils ont pas des générateurs qui garantissent de ne pas tirer deux fois le même numéro (donc cyclique d'ordre n+1 avec mon example)

[GaBuZoMeu]

Les mathématiques derrière ce que je propose :

Si est un nombre premier, le groupe multiplicatif de (formé des classes de nombres premiers avec , c;-à-d. l'ensemble de toutes les classes non nulles de ) est cyclique d'ordre . Ça veut dire qu'il existe un premier avec tel que les pour soient tous les entiers de 1 à . Bien entendu, si est premier avec , les pour sont aussi tous les entiers de 1 à .
Un tel s'appelle un générateur du groupe multiplicatif de . Il n'y a pas de procédé miracle pour trouver un générateur. Une fois qu'on a un tel générateur , il est facile de trouver les autres : ce sont les où est premier avec .

Si ça t'ennuie que le 0 ne soit pas produit par ce procédé, il suffit de décaler de 1 : tu as tous les entiers de 0 à , dans un désordre apparent.

[ogaland]

Merci !