IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

Décomposition minimale d'une permutation


Sujet :

Mathématiques

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé Avatar de Onimaru
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2010
    Messages
    283
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : Turquie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Mars 2010
    Messages : 283
    Par défaut Décomposition minimale d'une permutation
    Salut à tous je cherche un algorithme qui permet de trouver la permutation minimale qui transforme le vecteur A en B puis donne la décomposition minimale de cette permutation en produit de transpositions.

    Exemple (tri) :

    A : (4,3,0,4,3,1,1,1,2,4,3,3,2,3,4,4,1,1,3,4,2)
    B : (0,1,1,1,1,1,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4)

    Merci.

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    C'est un énoncé d'exercice, ou ca a une quelconque finalité (qu'on aimerait bien connaitre) ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre éclairé Avatar de Onimaru
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2010
    Messages
    283
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : Turquie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Mars 2010
    Messages : 283
    Par défaut Décomposition minimale d'une permutation
    Salut
    Tout a commencé quand je lisais l'article sur les permutations dans Wikipedia, plus précisément la partie décomposition des permutations en transpositions, je n'ai pas compris cet algorithme.

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Onimaru Voir le message
    Salut
    Tout a commencé quand je lisais l'article sur les permutations dans Wikipedia, plus précisément la partie décomposition des permutations en transpositions, je n'ai pas compris cet algorithme.
    Et bien le but est de trouver une suite de permutation (echange de 2 elements) qui transforme A en B.

    1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, puis cherche dans les elements restant celui qu'il faudrait mettre.
    2. L'algo effectue la permutation (et la note en mémoire).
    3. retour à l'étape 1, tant que A est différent de B

    Au final, on obtient la liste des permutations a effectuer pour transformer A en B
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Membre éclairé Avatar de Onimaru
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2010
    Messages
    283
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : Turquie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Mars 2010
    Messages : 283
    Par défaut Décomposition minimale d'une permutation
    Merci pour ton aide,
    Pour ne pas confondre les termes : la permutation est un ensemble de transpositions (permutation à deux) c'est comme ça?

    D'après ce que j'ai compris voici l'algorithme :
    (A, B les deux vecteurs en entrée, T vecteur temporaire pour générer la permutation).
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
     T := A; 
     for I := 1 to N do
      if B[I] <> T[I] then // pour laisser les points fixes.
       for J := I + 1 to N do // on cherche la première position qui satisfait la 
                                    // condition.
         if B[I] = T[J] then
          begin
           AddTransposition(AsTransposition(I, J)); // ajouter cette transposition à 
                                                                  // la permutation.
           Swap(T, AsTransposition(I, J)); // Modifier le vecteur temporaire.
           Break // pour ne pas ajouter une autre transposition pour le même 
                   // élément.
          end;
    Dites moi si mon algorithme est juste et si c'est le cas est ce qu'il donne la plus petite permutation qui transforme A en B ?
    Merci.

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Oui, cela m'a l'air d'être bon.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 54

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, puis cherche dans les elements restant celui qu'il faudrait mettre.
    2. L'algo effectue la permutation (et la note en mémoire).
    3. retour à l'étape 1, tant que A est différent de B
    Cet algo est correct dans le monde des permutations. Les gars, utilisons le langage standard:

    - une permutation est une bijection de (1...n) vers (1...n)
    - une transposition t(i,j) est la bijection switchant i et j et fixant le reste.

    L'algo décrit par Pseudocode fournit une décomposition minimale d'une permutation en composition de transpositions. C'est minimal, au sens où c'est le job "minimum", comme on le voit avec la représentation en tresse des permutations ci-dessous (désolé, je dessine mal).




    Donc ton exemple tu recherches une décomposition en transpositions te permettant de passant de ton vecteur A à B. Ok, c'est pas le monde des permutations, car des composantes de A et/ou B sont égales, mais Pseudo a adapté l'algo.Je pense qu'une précision s'impose dans son point 1:

    1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, soit Ai<>Bi, puis cherche dans les elements Aj ou j>i le premier élément vérifiant Aj=Bi et Bj<>Aj. On applique alors la transposition T(i,j), et comme dans le dessin ci-dessus on arrive à une décomposition "minimale".

  8. #8
    Membre éclairé Avatar de Onimaru
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2010
    Messages
    283
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : Turquie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Mars 2010
    Messages : 283
    Par défaut Décomposition minimale d'une permutation
    Ton idée parait intéressante et je crois c'est que je cherche pouvez vous l'écrire sous forme d'algorithme ? et moi de ma part je vais essayer.

  9. #9
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Nemerle Voir le message
    mais Pseudo a adapté l'algo.Je pense qu'une précision s'impose dans son point 1:

    1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, soit Ai<>Bi, puis cherche dans les elements Aj ou j>i le premier élément vérifiant Aj=Bi et Bj<>Aj. On applique alors la transposition T(i,j), et comme dans le dessin ci-dessus on arrive à une décomposition "minimale".
    Oui, mon explication n'était pas très rigoureuse mathématiquement parlant. J'essayais juste de résumer le principe de l'algo de Wikipedia en 3 phrases.

    Ca m'apprendra.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Décomposition minimale d'une permutation 2
    Par Onimaru dans le forum Mathématiques
    Réponses: 2
    Dernier message: 10/09/2010, 16h15
  2. [JavaScript] Taile minimale pour une fenêtre web
    Par efficks dans le forum Général JavaScript
    Réponses: 3
    Dernier message: 07/12/2005, 14h57
  3. Fixer une taille minimale d une fenetre
    Par anouar dans le forum Interfaces Graphiques en Java
    Réponses: 1
    Dernier message: 27/10/2005, 00h53
  4. dimensions minimale d'une page XHTML
    Par alxx160 dans le forum Balisage (X)HTML et validation W3C
    Réponses: 1
    Dernier message: 22/08/2005, 12h36
  5. [MFC]Taille minimale d'une fenetre
    Par fr66 dans le forum MFC
    Réponses: 5
    Dernier message: 14/06/2004, 11h44

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo