Problème Velu D'algorithmique, mélangeage d'un tableau sous contrainte

Hello,
j'ai un problème d'algorithmique à fortes contraintes que je voudrais vous soumettre, je pense que c'est un cas qu'on doit retrouver dans d'autres besoins que le mien. Si vous avez une soluce ou de la littérature à me conseiller, je suis preneur.

J'expose :
il me faudrait une fonction mélanger_tableau(tableau, clé) qui mélange les valeurs de tableau en fonction de la valeur de clé (de sorte que si on fourtnit le meme tableau et la meme clé on obtient toujours le même résultat). On doit bien sur retrouver toutes les valeurs de la distrib d'entrée dans la distrib de sortie.
Bon ca c'est simple mais la grosse contrainte c'est qu'il faudrait que l'algo garantisse que pour espace de valeur de clé (disons 1 à 100) on obtienne à peu près (à peu près= + ou - 10%) le même nombre pour chaque paire [valeur, indice dans le tableau].
Plus concrètement qu'on garantisse que chaque valeur se retrouve le même nombre de fois à chaque position.

en gros je prends mon tableau distribution initial TI[v1,v2,v3,...,v14]
je balance 100 fois mélanger_tableau(TI,1 à100)
j'obtiens 100 tableaux T1,T2,T3,....T100
si je les mets les un au dessus des autres et que je compte les nombre d'occurence de chaque V je voudrais avoir à peu près autant de V1 que de V2 que de Vx dans la colonne 1, pareil dan sla colonne 2 etc...

l'application de ça dans mon jeu (pour se accrocher à du concret) est de répartir des bonus (les V) sur les ressources naturelles(les indices) géographiquement (x-y me donne la clé) en garantissant que dans une province donnée on retrouvera bien à peu près le même nombre de fois toutes les valeurs différence de bonus pour chaque ressource.
illustration avec notre algo actuel :
http://www.the-continent.org/site/cartes_ressources.php
on voit que la répartition est totalement inégale sur certaines denrées (bois, bétail, peaux...)

voilivoilo. Si vou sconnaissez d'autres fofo de devs chevronnés ou je pourrai poster ça m'intéresse aussi.
zumba

[HS]10 essais pour répondre, je ne sais pas si c'est le forum qui a du mal, mais bon [/HS]

Alors, je te rpopose un moyen super simple, qui devrait, à vue de nez (et je l'ai long), résoudre ton problème :

Suivant la clé utilisée, tu rajoutes celle-ci à l'indice utilisé au départ, modulo le nombre d'éléments -1. Tu choisis l'élément de départ égal à la clé.

Pour clé = 1, les valeurs sont placées dans le même ordre que le tableau de base, déclaés de 1 (puisque la clé vaut 1 et que le premier élément vaut 0).
Pour clé=2, les valeurs sont placées dans le même ordre, mais décalées de 2 en 2 :
2, 4, 6, etc..., 98, 100 (modulo 99, donc 1), 3, 5, etc..., 99 (modulo 99, donc 0)

A priori, les valeurs seront forcément distribuées de manière régulière (si je me trompe pas, mais là c'est du pif, plus du nez )
En tout cas, ca reste super simple et surement rapide. La même clé donne toujours le même résultat. Tu peux augmenter la taille du tableau sans souci, etc...

Le modulo, ca sauve la vie

Le problème de l'algorithme précédent est qu'il garantit une distribution beaucoup trop homogène, ce n'est pas naturel. Il est normal qu'il y ait des inégalités : ça s'appelle le hasard !
De plus j'ai peur que pour certaines valeurs on ne puisse pas aller au bout de l'algorithme, je pense notamment aux clés multiples de longueur(tableau)-1, à vue de nez cela pourrait poser des problèmes.

De toute façon soit tu acceptes qu'il puisse y avoir des inégalités (le hasard ne donne une distribution équitable que sur de très grands nombres d'essais) soit tu renonces au hasard et tu ne pourras alors pas obtenir d'allure aléatoire de ta distribution.

Personnellement j'aime bien partir de ce qui existe déjà, donc j'aurais utilisé les mt_rand() de PHP.
En spécifiant mt_srand($clé) je suis sûr que l'algo se comportera toujours de la même façon pour la même valeur de $clé.
Et même avec un peu de chance array_shuffle() se base sur mt_srand(), je vais tester et je reviens te dire ça.

Je peux te proposer ça, à double avantage :
- vraiment aléatoire, puisque basé sur mt_rand()
- algo à cout fini, il est O(n) (n la longueur du tableau)
a priori il devrait offrir une répartition homogène puisqu'il est basé sur un aléatoire robuste, mais c'est à vérifier :

Edit : remise en forme du code

Hello,
Merci pour vos réponses ! en effet il faut tout d emême un caractère aléatoire dans
Naholyr, encore une fois ton aide m'est précieuse (tu m'avais déjà fourni un algo d'ordonancement de poules sportives qui marche du tonnere). On va étudier ce code et tenter de l'implémenter. Je te tiens au courant !

A+ et merci.