Discussion :

[isangoma]

Bonjour,

Je cherche une fonction (ou comment créer une telle fonction) telle que :
f(a) = b;
f(b) = a;
a,b sont des entiers compris entre [0,N], N quelconque.
Le but est que le rapport entre 'a' et 'b' semble aléatoire.

J'ai regardé du coté des fonctions de chiffrement comme XTEA, mais ces fonctions ne semblent fonctionner que pour certaines valeurs de N (des puissances de 2 en particulier).
Il est aussi possible de prendre un tableau avec toutes les valeurs de 0 à N, puis de le mélanger, à condition de n'échanger les indexs qu'une seule fois. Cependant, cela demande de recalculer le tableau ou de le stocker quelque part. Et c'est moins élégant qu'une fonction bijective.

Donc si vous avez une idée du type de fonction qui pourrait me convenir, je vous remercie.

[Flodelarab]

Bonjour

Tu dis des choses contradictoires:

• f(a) = b;f(b) = a; Ça, ça exprime un échange.

• un tableau avec toutes les valeurs de 0 à N, puis de le mélanger

  Ça, ça exprime une permutation.

Ce n'est pas pareil.


Si tu cherches un échange de 2 valeurs, ta fonction dépendra de ces 2 valeurs. Est-ce bien ce que tu veux ?
Tu peux faire un échange classique avec 3 variables: a->c; b->a; c->b;
Ou un échange à 2 variables avec un OU_exclusif: x = x XOR y; y = x XOR y; x = x XOR y
Ou enfin une fonction f telle que f(x)=a+b-x. Ainsi f(a)=b et f(b)=a.


Si tu cherches une permutation de N+1 valeurs, sur un ensemble [0;N], tu peux utiliser le reste de la division entière (ou modulo)
Exemple sur [0;15] => modulo 16, on obtient la permutation suivante (en ajoutant 7 à chaque fois):
5+7=12 =12[16]
12+7=19 =3[16]
3+7=10 =10[16]
10+7=17 =1[16]
...
5 -> 12 -> 3 -> 10 -> 1 -> 8 -> 15 -> 6 -> 13 -> 4 -> 11 -> 2 -> 9 -> 0 -> 7 -> 14 -> 5 -> 12 ... etc

Le modulo ne sert qu'à contraindre le retour dans l'intervalle. A toi d'inventer n'importe quelle fonction si celle donnée ne te plaît pas.

[picodev]

Bonjour,
Je pense que Isangoma cherche plutôt une fonction involutive→ f(f(x))=x qui aurait la propriété f(x)≠x.
Il y a des fonctions simples qui correspondraient, comme f(x)=x XOR C, où C est une constante convenablement choisie. Cela correspondrait effectivement à une permutation qui serait un dérangement involutif. On peut aussi utiliser un dérangement involutif pour mélanger les bits de la représentation binaire de x, enfin à vérifier, je dis ça comme ça par intuition.
À noter aussi que la composée de deux involutions est involutive ssi les deux involutions commutent. Cela permet d'en créer de nouvelles.

[isangoma]

Bonjour,
Merci a vous deux pour vos réponses.

Je vais tenter de poser mon problème de manière plus claire.
J'ai N numéros de série consécutifs compris entre 0 et N. Mais je ne veux pas que l'ordre dans lequel les produits soient numérotés suivent l'ordre des entiers.
Par exemple, au lieu d'imprimer la suite [0,1,2,3,4,...,N], je veux imprimer la suite [42,125,12,99,1,...] qui doit sembler aléatoire.
Cependant j'ai plusieurs contraintes.
Connaissant le numéro de série imprimé, je doit pouvoir retrouver le moment de son impression (ici, '12' est le troisième numéro de série).
La taille maximum est borné le plus souvent par une puissance de 10, mais pas toujours, et la puissance peut varier. Donc la fonction doit pouvoir s'adapter à ça.

Je suis d'accord que mon tableau avec permutation ne répond pas au critère pour une fonction involutive (Merci Picodev, ce mot va bien m'aider).
Cependant, si je connais N et la manière de faire la permutation, je peux satisfaire mes contraintes. C'est juste que cette solution n'est pas la plus rapide ni la plus élégante.

L'idée du modulo, pourquoi pas. Mais je n'ai pas compris comment retrouver l'index sans recalculer toute la chaîne (même problème que le tableau permuté donc).

Les involutions, je ne connais pas, mais cela pourrait convenir. Je vais regarder cela.
La simple fonction XOR ne semble pas convenir, car si un seul bit change entre deux numéro de série consécutif, alors un seul bit va changer entre les deux résultats.
Mais je vais regarder de ce coté quand même.

[edit] Pour le modulo je n'ai rien dit, c'est simple a inverser en fait.
13+7 = 20[16] = 4;
4+16 = 20; 20-7 = 13;
Parfois je ne réfléchis pas suffisamment.
Mais du coup comment trouver A et B (ici 7 et 16) pour être sur de couvrir tout l'ensemble. Suffit-il que A et B soient premier entre eux ?
Et puis il y a toujours le problème de devoir calculer toute la chaîne en une fois et de ne pas pouvoir calculer les éléments indépendamment.

[Flodelarab]

La fonction réciproque de "+7" est "+9" car 9+7=16
4+9=13 [16]
13+7=4 [16]

7 et 9 sont dits "générateurs" du groupe cyclique Z/16Z car ils permettent de recréer tous les autres.

Effectivement, Z/nZ est cyclique, x est un générateur si et seulement si x est premier avec n. (ici, n=16)

[isangoma]

Bon j'écris bêtises sur bêtises.

Effectivement, je peux calculer l'inverse. Mais l'inverse ne fait que me donner l'élément précédent de la chaîne, non son index.
Ce dont j'ai besoin c'est de retrouver son index.
Du coup le problème est toujours le même qu'avec le tableau, je dois tout recalculer pour retrouver la position dans la chaîne d'une valeur.

[Flodelarab]

Est-ce qu'on peut avoir un énoncé ?
Qu'est-ce que ce tableau ?
Quelles sont les valeurs ?
Quels sont les indices ?
Pourquoi s'embêter avec un tableau si c'est juste pour avoir des numéros de série ?

Effectivement, je peux calculer l'inverse. Mais l'inverse ne fait que me donner l'élément précédent de la chaîne, non son index.

Et bien, fais la permutation sur les indices, pas sur les valeurs...

[isangoma]

Merci pour l'aide.

Il n'y a pas d'énoncé a proprement parler.
J'ai tenté de décrire le problème dans mon second message, mais apparemment ce n'était pas suffisamment clair.

En gros, je voudrais une suite S de N+1 entiers dans l'interval [0,N], qui contient tous les entiers dans cet interval une fois et une seule.
Cette suite doit sembler aléatoire, donc aucun lien évident entre S_i et S_i+1.
Et il me faut une fonction f telle que f(i) = S_i et f(S_i) = i.
Je ne sais pas si je suis plus clair.
Désolé si ce n'est pas le cas.

Dans ma recherche, je suis tombé sur cette page : Permutation Involution
Cela semble correspondre à mon problème, mais je ne trouve pas de fonction qui me permette de calculer simplement cette permutation.

[Flodelarab]

f(i) = Si et f(Si) = i.

Hum. C'est ce qu'on a fait:
L'objet d'indice 13 est 4.
L'objet dont la valeur est 4 est d'indice 13.

Tu veux que f = f^-1 ?
C'est impossible car on ajouterait la moitié de n pour revenir au point de départ. Et ce nombre ne serait alors pas premier avec n.

Où est le problème ?
pourquoi f(i)=Vi et g(Vi)=i ne te convient pas ?

[picodev]

[...]
Tu veux que f = f^-1 ?
C'est impossible car on ajouterait la moitié de n pour revenir au point de départ. Et ce nombre ne serait alors pas premier avec n.
[...]

C'est possible, c'est par définition une fonction involutive …
Par exemple dans ℝ^* on f(x)=1/x est involutive.
Avec les entiers de [0;2ⁿ-1] f(x)=x XOR (2ⁿ-1) en est une aussi.

Merci pour l'aide.

Il n'y a pas d'énoncé a proprement parler.
J'ai tenté de décrire le problème dans mon second message, mais apparemment ce n'était pas suffisamment clair.

En gros, je voudrais une suite S de N+1 entiers dans l'interval [0,N], qui contient tous les entiers dans cet interval une fois et une seule.
Cette suite doit sembler aléatoire, donc aucun lien évident entre S_i et S_i+1.
Et il me faut une fonction f telle que f(i) = S_i et f(S_i) = i.
Je ne sais pas si je suis plus clair.
Désolé si ce n'est pas le cas.

Dans ma recherche, je suis tombé sur cette page : Permutation Involution
Cela semble correspondre à mon problème, mais je ne trouve pas de fonction qui me permette de calculer simplement cette permutation.

Pour de la doc tu peux chercher sur «fixed point free involution» les involutions ( f(f(x)=x ou f=f^-1 ) sans points fixes (sans n tel que f(n)=n).

→ Generating involutions, derangements, and relatives by ECO
→ An Algorithm to List All the Fixed-Point Free Involutions on a Finite Set

[isangoma]

Encore merci.
Mais je ne vois pas comment je récupère l'index.
L'exemple ne m'aide pas.
Si on prend module 16 et une somme de +7 on a la suite (et leur index en dessous) :
00->07->14->05->12->03->10->01->08->15->06->13->04->11->02->09->00
00->01->02->03->04->05->06->07->08->09->10->11->12->13->14->15->00(16)

Je comprend comment calculer la valeur V_i+1 a partir de la valeur V_i.
Je comprend aussi comment calculer la valeur V_i-1 a partir de la valeur V_i.
Mais pas comment calculer la valeur V_i uniquement a partir de i (sans calculer les valeurs précédentes donc), ni comment calculer i à partir de V_i.

pourquoi f(i)=Vi et g(Vi)=i ne te convient pas ?

Cela me convient parfaitement. Mais je ne vois pas comment trouver ces fonctions pour le modulo.


Merci Picodev, je vais aller lire ces liens.

[picodev]

Si tu veux une involution à partir du +7 modulo 16 →

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
fonction F(n : entier) : entier
début
  si est_pair(entier) alors
    F ← (entier + 7) modulo 16
  sinon
    F ← (entier + 9) modulo 16
  fin si
fin.

[Flodelarab]

comment calculer la valeur Vi uniquement a partir de i

Vi=7*i [16]

exemple:
i=11
Vi=11*7 % 16 = 77 % 16 = 13

ni comment calculer i à partir de Vi.

i=7*Vi [16]

exemple:
Vi=13
i=13*7 % 16 = 91 % 16 = 11

Car 7 est l'inverse de 7. (coïncidence 7*7=49=48+1=3*16+1)

[isangoma]

Ok, je suis une andouille, merci à vous deux.
Merci Picodev pour m'avoir fait comprendre ce que Flodelarab me mettait sous le nez depuis ce matin.
Désolé Flodelarab pour avoir été si long à comprendre.

Alors oui les modulo semblent répondre à ma problématique. Il suffit juste de bien choisir les valeurs de départ.

Je vais quand même aller jeter un oeil aux deux papiers.

[tbc92]

Pour bien choisir les valeurs n=7 et E=16, il suffit de prendre n et E premiers entre eux.
Et comme E peut varier, il suffit que tu prennes n = un nombre premier très grand.

[isangoma]

Effectivement.
Le plus casse pied est de calculer l'inverse. J'ai trouvé un algo, mais sur les grand nombre il semble un poil long.

[tbc92]

E=16
n = 7
for i = 1 to E
if mod(i*n, E ) = 1 then
inv = i
exit Loop
end if
end loop