Re: permutation sur N quelconque / polynomes de permutation

Le 25/08/2024 à 19:57, robby a écrit :

Le 24/08/2024 à 22:04, efji a écrit :

OK, oui bien sûr, tu aurais donner le contexte d'utilisation.

 non: la question se suffisait, sauf pour les gens qui veulent tourner autour du pot ;-)

OK, je vois le genre du mec qui donne super envie de l'aider...
Bien sûr que non la question ne suffisait pas et elle était super mal posée. Quand on demande un truc "rapide" pour faire un machin "de taille N", tout le monde comprend qu'on cherche un algo efficace pour N grand, pas qu'on va effectuer des milliards de fois l'action pour N=5. Par exemple il y a des milliers de gens qui travaillent sur les résolutions de systèmes linéaires de grande taille et personne qui cherche à optimiser les systèmes 2x2.

 

Pratiquement sûr qu'il existe des implémentations rapides sur GPU de ce genre de choses.

 Oh, comme ça aide ;-)
 Bref, je cherche une fonction style hachage, pas un algorithme.

Chercher la définition du mot "algorithme" peut-être ?
Il va cracher les valeurs de N qui l'intéressent ou bien il continue ses sarcasmes ?
Rappel: il y a N! permutations de {1,..,N}, donc pour N>15 on peut oublier la fonction de hashage.

 La je viens de me remettre aux polynomes de permutation,
par ex perm(i) = mod( a.i³, N ).
Pour N premier c'est facile, mais dans les autres cas je n'ai rien compris a l'explication dans https://en.wikipedia.org/wiki/Permutation_polynomial#Higher_degree_polynomials
( ça se base sur des produits d'espaces quotientés, beurk ). Quelqu'un comprend ?
 A minima pour N' un peu en dessous d'un nombre premier N, on peut a très faible surcout se contenter de compacter le range en suivant le graphe quand on tombe sur un nombre > N'.
 exemple pour générer des permutations sur 1...81 , en utilisant N=83:
https://www.desmos.com/calculator/ykmoljie7i
https://www.shadertoy.com/view/Xc2Bzz

C'est pas des algorithmes... :)

 je m'en etais d'ailleurs servi pour programmer les jeux SET https://www.shadertoy.com/view/McjBRz et une base pour Memory https://www.shadertoy.com/view/lXlSzf
 ( mais l'usage haute performance, c'est plutôt pour le sampling, les matériaux texturés, etc ;-) )
 

--
F.J.