Discussion :

[sbadecoder]

Bonjour à tous,

Je dispose sous delphi de deux tableaux :

Code :

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

1
2
3
 
TAB : array[0..999999] of char;  // 1 million de lettres 'A' .. 'Z'
TAB2 : array[0..9] of integer;  // 10 index de TAB qui doivent rester fixes

Exemple :
si TAB2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
alors le mélange portant sur TAB doit conserver les 10ers caractères à leur place et mélanger le reste du tableau TAB.
TAB2 pouvant contenir n'importe quelle valeur entre 0 et 999999.

Objectifs:
Mélanger le plus rapidement et le plus aléatoirement possible le tableau TAB, en respectant les directives de TAB2, et sans changer la fréquence de chaque lettre. (cela doit être rapide, car je dois effectuer ce mélange un grand nombre de fois...)

[pseudocode]

L'algorithme de Fisher & Yates est en O(n).

(click me)

Pour tenir compte de tes contraintes il faut ajouter un test pour savoir si on tente de swapper des cases interdites, et proceder a un nouveau tirage. Ca va rajouter quelques tours de boucles, mais avec un ratio de 10/1.000.000 ca ne devrait pas trop se sentir.

[sbadecoder]

Merci.