[Algorithmie] [C] Problème shuffle "Fisher and Yates' original method"

Bonjour,

j’ai essayé de programmer une méthode de mélange, pour cela j’ai créé une fonction int* shuffle(int n), qui à un entier n renvoie une possibilité d’ordre pour les naturels < n. En clair, shuffle(3) devra renvoyer [0, 1, 2] ou [0, 2, 1] ou [2, 1, 0] etc..

Pour cela, j’ai voulu implémenter le Fisher and Yates’_original_method

Voici mon code:

int* shuffle(int len){
    int  * ret = (int*)malloc(sizeof(int)*len);
    char * LL  = (char*)malloc(sizeof(char)*len);
    memset(LL, 1, len);
    int pnt = 0;
    int i = len-1;
    int delta;

    while(i >= 0){
        delta = rand_int(0, i);
        pnt = 0;
        while(delta > 0 || LL[pnt] == 0){
            pnt++;  
            if (LL[pnt]){
                delta--;
            }
        }
        ret[len-(i+1)] = pnt;
        LL[pnt] = 0;
        i--;
    }
    free(LL);
    return ret;
}

rand_int(int a, int b) renvoie un entier de [a, b]; LL[] vaut 0 pour la ième place si i appartient déja à ret, qui est le tableau renvoyé.

Le problème est, quand je test quelque chose du genre :

    for (int i = 0; i < 10000; ++i)
    {   int* t = shuffle(10);
        for(int j=0; j<10; j++){
            printf("%i", t[j]);
        }
        puts("");
    }

Et que je test avec:

./a.out | grep 9$ | wc -l

J’obtient à peu près 5000, c’est à dire que la moitié des listes renvoyées finissent par 9, ce qui n’est pas normal…

Voyez vous ou est le problème ? Merci d’avance !

J’ai du mal à comprendre ton algorithme.

Principalement car je pense que ce n’est pas une implémentation du mélange de Knuth.

En effet, si j’ai bien compris. Tu te sers de LL comme d’un générateur de nombre. Je n’ai pas bien compris comment, c’est sensé marcher. Mais ta manière de faire me parait bancale.

Si j’ai bien compris. LL te sert de booléen pour savoir si un nombre a déjà été utilisé.

Le problème c’est que $9$ ne peut être choisi par delta qu’une seul fois. Le premier passage de boucle. Après, delta sera inférieur à $9$. Ensuite, j’ai pas bien compris pourquoi, mais tu affectes comme valeur delta + nombre_de_valeur_affecte_inf_delta en gros.

Tu as $9/10 * (1/9)$ de sortir $9$. Soit $1/10$. Ouais, je vois où tu veux en venir… Mais il doit y avoir un problème d’implémentation.

Bref, suit l’algo à la lettre plutôt que de partir sur une version perso de l’algo. C’est trop compliqué à comprendre en détail.

PS: Ce que je comprend pas dans ton algo, c’est pourquoi tu vérifies LL[ptn+1]. Passer la ligne 13 après le if me semble plus logique. Sinon, on se trouve dans le cas, le premier est $0$, le deuxième $delta = 8$, donc on ne gagne jamais le +1 et donc on reste à $8$.

Oui oui oui !

Le problème était bien que je checkais LL[pnt+1] et pas LL[pnt] !

Merci beaucoup !

En effet l’algo est assez moche, parce que c’est même pas une version perso mais une invention entièrement personnel Et j’ai vu après coup que cela se nommait "methode original etc."

En tout cas merci de m’avoir servi de canard en plastique

(Je plaisante, ca faisait 2h que je le faisais et ca ne marchait pas :,( )

Je te conseil de vraiment suivre l’algo. C’est à dire de créer en premier lieux les valeurs. Et ensuite de les mélanger avec des échanges.

Ça t’évitera des pépins.

L’algo de base, c’est du $O(n)$. Ton algo, c’est du $O(n^2)$ si j’ai bien compris.

PS: Je me permet de mettre les tags et en résolu.