Je cherche à déterminer une fonction bijective paramétrée (et sa réciproque), de [|0;n[| vers [|0;n[| (bref, l'ensemble des n entiers compris entre 0 et n-1), telle que l'ensemble résultat soit une permutation la plus chaotique possible de l'ensemble de départ, la permutation obtenue variant selon la valeur du paramètre.
Comme le terme chaotique est un peu vague, pour préciser ma pensée, il faudrait que, si l'on considère toutes les permutations que permet d'obtenir la fonction, aucun nombre ne soit statistiquement plus souvent voisin de certains nombres que d'autres.
Comme en plus il s'agit de l'implémenter dans un programme et de la faire tourner plusieurs centaines (milliers ?) de fois par secondes, je serai obligé de me restreindre à des calculs pas trop gourmands, pour la fonction et pour sa réciproque.
Pour mieux illustrer mon problème, de peur que tout ceci ne semble un peu confus, j'utilisai jusqu'à présent la fonction :
fa,n:x -> (a*x)%n
(Il s'agit du modulo informatique, qui renvoie l'entier congruent compris entre 0 et n-1.)
Pour que la fonction corresponde au critères, il faut que a soit premier avec n. Il est inutile que a soit supérieur à n/2 car au-delà, ce seront de nouveau les même permutations ou leurs inversées. La réciproque se calcule facilement.
Ainsi, par exemple, pour n=10, on pourra prendre a=1 ou a=3, ou pour n=15 a=1, a=2 ou a=4 et ainsi :
- Code: Tout sélectionner
a| 1| 3 a| 1| 2| 4
--------- ------------
0| 0| 0 0| 0| 0| 0
1| 1| 3 1| 1| 2| 4
2| 2| 6 2| 2| 4| 8
3| 3| 9 3| 3| 6|12
4| 4| 2 4| 4| 8| 1
5| 5| 5 5| 5|10| 5
6| 6| 8 6| 6|12| 9
7| 7| 1 7| 7|14|13
8| 8| 4 8| 8| 1| 2
9| 9| 7 9| 9| 3| 6
10|10| 5|10
11|11| 7|14
12|12| 9| 3
13|13|11| 7
14|14|13|11
C'est pas trop mal, mais il reste quelque défauts. Si on passe sur le fait que ça reste très régulier pour un ensemble chaotique, et que ça ne permet d'obtenir qu'une infime portion des permutations possibles, le plus important, de loin, est que a dépend de n, et que malgré donc la simplicité du calcul, je doive d'abord calculer la décomposition de n (pouvant être très grand) en facteurs premiers.
En gros, j'aimerais donc trouver une nouvelle fonction plus à même de répondre à mes attentes, mais n'étant pas une flèche en mathématiques, je n'ai plus du tout d'idées. Du coup, je me tourne humblement vers vous, en espérant que mon problème suscite chez vous de l'intérêt, et que vous puissiez me donner quelques pistes. :happy2:
Cordialement,