Forum Programmation.autre Algorithme : permutation

Posté par  (site web personnel) . Licence CC By‑SA.
Étiquettes : aucune
2
25
juin
2014

Le besoin pressant d'un univers logique et cohérent est profondément ancré dans l'inconscient humain. Mais l'univers réel est toujours à un pas au-delà de la logique.

Je me suis pris la tête aujourd'hui avec un collègue sur un calcul tout simple ; Imaginons que nous ayons une feuille, avec 4 bord :

#define HAUT = 0;
#define DROITE = 1;
#define BAS = 2;
#define GAUCHE = 3;

et un tableau avec des valeurs pour chaque bord :

int marges[4];

il est facile de déterminer la marge à charger si la page a été tournée :

int getNewIndice(int angle, int indice) { // renommé en getNewIndice suite à remarque en commentaire

    switch (angle) {

        case 90:     return (indice + 1) % 4;
        case 180:    return (indice + 2) % 4;
        case 270:    return (indice + 3) % 4;
        default:     return indice;

    }

}

Ça marche parce que les données sont ordonnée dans l'ordre de rotation. Sauf que dans notre cas, le tableau était construit avec les indices suivants :

#define HAUT = 0;
#define BAS = 1;
#define GAUCHE = 2;
#define DROITE = 3;

il va de soit que ces valeurs sont définies et ne peuvent pas être changées. On a fini en énumérant les 3 cas possibles de rotation, et mettant dans le code les 3 combinaisons possibles, ce qui marche dans ce cas assez simple. Pourtant, je me demande s'il y a une manière simple de calculer l'indice à charger. Je pense qu'il doit s'agit d'une histoire de permutation, mais je ne vois pas trop l'algorithme qui pourrait faire ça.

Je viens donc solliciter vos avis, si quelqu'un a une idée là dessus. (J'ai donné l'exemple en C, mais n'importe quel langage fera l'affaire)

  • # ca marche ton truc ?

    Posté par  . Évalué à 2.

    une fonction indice qui s'appelle elle meme en parametre indice ???

    int indice(int angle, int indice) {

    bon sinon, je ne sais pas à quoi fait reference ton indice, mais tu peux utiliser un tableau nommé
    tu as des valeurs definies plus haut
    indice[HAUT] c'est la meme chose que indice[0]

    • [^] # Re: ca marche ton truc ?

      Posté par  (site web personnel) . Évalué à 2.

      une fonction indice qui s'appelle elle meme en parametre indice ???

      J'ai écrit le code pour le forum, il s'agit (plus ou moins) du cas réel (ça n'est pas du C à la base), mais je n'ai pas cherché à le compiler avant de poster. Je me permet de d'appeler la fonction fautive ici sous le nom getNewIndice pour être plus clair…

      indice[HAUT] c'est la meme chose que indice[0]

      Je suis d'accord. La question qui se pose est après la rotation de la page.

      après rotation de 90° (si le tableau est ordonné dans l'ordre HAUT, DROIT, BAS, GAUCHE) :

      margeHaute = marge[getNewIndice(90, HAUT)];
margeBasse = marge[getNewIndice(90, BAS)];

      (avec la méthode getNewIndice correspondant à la fonction donnée dans le post d'origine).

      par contre, si le tableau est ordonné dans l'ordre HAUT, BAS, GAUCHE, DROIT, je ne vois pas comment construire la fonction getNewIndice pour avoir le même résultat. Je pense qu'il s'agit plus d'une question de math (d'où mon titre sur les permutations), et je ne sais pas trop comment appréhender la chose simplement.

      • [^] # Commentaire supprimé

        Posté par  . Évalué à 5.

        Ce commentaire a été supprimé par l’équipe de modération.

        • [^] # Re: ca marche ton truc ?

          Posté par  (site web personnel) . Évalué à 2.

          Effectivement, je pense que l'idée de convertir dans l'ordre dans un repère, puis appliquer l'opération inverse est une bonne piste.

          J'étais parti dans quelque chose de beaucoup plus compliqué (arrangements etc), qui au final n'avait débouché sur rien.

          Merci !

          • [^] # Re: ca marche ton truc ?

            Posté par  . Évalué à 5.

            Il me semble qu'une solution plus robuste (du point de vue humain) serait d'écrire:

            int perminv[] = {HAUT, DROITE, BAS, GAUCHE};

            Et de se rendre compte que perm[i] c'est équivalent à perminv[perminv[i]]. Ça limite les erreurs évoquées plus loin vu qu'on entre un seul tableau de conversion et ce de manière compréhensible.

        • [^] # Re: ca marche ton truc ?

          Posté par  . Évalué à 2. Dernière modification le 26 juin 2014 à 14:12.

          Je pense que ta fonction peut être résumée par :

          Non, car tu ne limites pas les valeurs au 3 angles requis (90, 180, 270). Si tu mets 360 + 180 = 540 tu vas renvoyer une rotation, alors qu'on doit renvoyer indice d'après le code d'exemple.
          il faudrait ajouter un test du genre : 

          if ( (angle >0) && (angle <360) && (angle % 90 == 0) && (indice >=0) && (indice < 4))
   ...;
else
   return indice;

  • # Utilise un tableau de conversion d'indice ?

    Posté par  (site web personnel) . Évalué à 4. Dernière modification le 26 juin 2014 à 00:05.

    Ton code marche pour :

        #define HAUT = 0;
    #define DROITE = 1;
    #define BAS = 2;
    #define GAUCHE = 3;

    Sauf que pas de bol, les valeurs sont :

        #define HAUT = 0;
    #define BAS = 1;
    #define GAUCHE = 2;
    #define DROITE = 3;

    Bon ben suffit de convertir en utilisant des tableaux :

        int conv[] = {0, 2, 3, 1};
    int convinv[] = {0, 3, 1, 2};

    Puis :

        int getNewIndice(int angle, int indice) {
        indice = conv[indice];
        int res = indice;
        switch (angle) {
            case 90:     res = (indice + 1) % 4; break;
            case 180:    res = (indice + 2) % 4; break;
            case 270:    res = (indice + 3) % 4; break;
        }
        return convinv[res];
    }

    Je n'ai pas testé, il est tard, mais tu vois l'idée…

  • # Polynome de degré 3 ou la version enclume flottante pour entiers

    Posté par  (site web personnel) . Évalué à 4.

    P(0)=0
    P(1)=2
    P(2)=3
    P(3)=1

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.