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

Algorithmes et structures de données Discussion :

Enumération de l'arrangement Anp


Sujet :

Algorithmes et structures de données

  1. #1
    Membre éclairé

    Homme Profil pro
    Fondateur de ZetaPush - realtime BaaS
    Inscrit en
    Mars 2002
    Messages
    146
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Fondateur de ZetaPush - realtime BaaS
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mars 2002
    Messages : 146
    Points : 687
    Points
    687
    Par défaut [Résolu] Enumération de l'arrangement Anp
    Bonjour à tous,

    J'ai trouvé le code pour énumérer tous les Cnp mais par contre, pour ce qui est des arrangements, je n'ai rien trouvé.

    Mon but, enumérer tous les arrangement possibles de n élément parmis p. Par exemple, j'ai l'ensemble {a,b,c,d,e}, je voudrais connaitre tous les arrangement de 2 éléments parmis cet ensemble.: aa, ab, ba, ac, ca, ...

    Un rappel, je sais calculer le nombre de solutions possibles, il me faut les énumérer toutes.

    Merci de votre aide,
    Mikaël Morvan
    ZetaPush: realtime BaaS www.zetapush.com

  2. #2
    Membre éclairé

    Homme Profil pro
    Fondateur de ZetaPush - realtime BaaS
    Inscrit en
    Mars 2002
    Messages
    146
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Fondateur de ZetaPush - realtime BaaS
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mars 2002
    Messages : 146
    Points : 687
    Points
    687
    Par défaut
    Le nombre 2 était mis là pour l'exemple, en fait le code doit permettre de faire par exemple A10 15, c'est à dire dans ton cas 10 boucles imbriquées...

    Merci quand même
    ZetaPush: realtime BaaS www.zetapush.com

  3. #3
    Expert éminent sénior
    Avatar de Guigui_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2002
    Messages
    1 864
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2002
    Messages : 1 864
    Points : 10 067
    Points
    10 067
    Par défaut
    J 'ai peut - etre une idée

    tu cree un tableau-compteur ayant autant de case qu 'il a d'elements (n)

    puis tu cree un compteur recursif :

    puis tu fais une boucle infini
    a chaque fois:

    {
    tu ajoutes 1 dans la derniere colonne, si le nombre est 2, tu met 0 et tu ajoute 1 dans la colonne d'avant. si le nombre de cette derniere devient 2 alors tu mets 0 et tu ajoutes 1 dans la colonne encore d'avant

    puis tu compte le nombre de 1 que tu as dans ton tableau, si y'en a p, tu recupere tous les elements qui sont a 1 dans le tableau correspondants
    }


    tu ne quitte la boucle que quand ton tableau est rempli de 1

    tu as donc besoin de creer une petite fonction recursive (externer a la boucle)

    C ' est pas ce qu 'il y a d'optimal, mais si n n'est pas trop grand, ca marche bien.

    pour ta reponse, j'avais remarque apres avoir envoye le post (mais je l'ai efface entre temps)

  4. #4
    Expert éminent sénior
    Avatar de Guigui_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2002
    Messages
    1 864
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2002
    Messages : 1 864
    Points : 10 067
    Points
    10 067
    Par défaut
    en fait, ce que je t'ai dit permet de récupérer les Cnp

    si je me souviens bien de la difference entre Anp et Cnp, une fois que tu as les Cnp (tu as deja trouve le code tu as dit), il suffit pour chaque element de ton cnp et rechercher toutes les permutations correspondant (c'est a dire tous les combinaisons possibles avec les p elements choisis)

    par contre , pour l'instant j'ai pas trop d'idée

  5. #5
    Membre habitué

    Profil pro
    Inscrit en
    Octobre 2002
    Messages
    66
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2002
    Messages : 66
    Points : 129
    Points
    129
    Par défaut
    On peut envisager quelque chose d'assez simple de prime abord : tu reprends les algos pour les Cnp mais en plus tu stockes tes résultats au lieu seulement de les afficher. Mais tu les stockes triés : ex: cab -> abc, de sorte que tu pourras éliminer à la récursion suivante les valeurs qui ne donneraient qu'une simple permutation de ce que tu as déjà trouvé !

    A+
    Consultez :
    - La F.A.Q Delphi + Les Cours Delphi
    - La sélection des Freewares Delphi

  6. #6
    Expert éminent sénior
    Avatar de Guigui_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2002
    Messages
    1 864
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2002
    Messages : 1 864
    Points : 10 067
    Points
    10 067
    Par défaut
    une autre idée: pour recuperer toutes les combinaisons possibles App (p elements parmi p)

    tu crées d'abord une structure d'arbre

    apres tu appelles la fonction Arbre.Comb (ListnElement)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    function Arbre.Comb (List listp)
    var
      i:integer;
    begin
      for i=0 to listn.count - 1 do
        begin
        creer sous-arbre (liste(i));
        Arbre.fils(i).Comb (liste \ element i);
        end;
    end;
    L'arbre va représenter l'ensemble des permutations possibles

    Puis une fois que tu as ton arbre, il faut une fonction qui récupère chaque branche (de taille p)
    c'est pas tres clair pour l'instant , mais je reflechis pour mettre une explication (developpement des autres fonctions)

  7. #7
    Expert éminent sénior
    Avatar de Guigui_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2002
    Messages
    1 864
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2002
    Messages : 1 864
    Points : 10 067
    Points
    10 067
    Par défaut
    voilà un prog qui permet de créer l'arbre des permutations
    je l'ai fait en delphi

    prog principale :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    var 
      l:TList;
       MonArbre:Arbre;
     
    begin
      l:=TList.Create;
      MonArbre:=Arbre.Create(0);
      l.Add(Pointer(1));
      l.Add(Pointer(2));
      l.Add(Pointer(3));
      l.Add(Pointer(4));
      MonArbre.Permutation(l);
    end;
    je travaille sur la recuperation. Pour l'instant, je n'arrive pas à tous les recuperer (du moins j'en perd quelques -uns en route

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    unit Unit2;
     
    interface
     
    uses classes, comctrls, math;
     
    type  Arbre=class
     
      public
        pere:Integer	;
      listfils:TList;
      procedure add(Fils:Integer);
      constructor create(Noeud:Integer); overload;
      procedure Permutation(ListNoeud:TList);
      end;
     
    implementation
     
    constructor Arbre.create(Noeud:integer);
    begin
      Pere:=Noeud;
      ListFils:=TList.Create;
    end;
     
    procedure Arbre.add(Fils:integer);
    var
      Arbreaajouter:Arbre;
    begin
       Arbreaajouter:=Arbre.Create(Fils);
       listfils.Add(arbreaajouter);
    end;
     
     
     
    procedure Arbre.Permutation(ListNoeud:TList);
    var
      i,j:Integer;
      ListCopie:TList;
    begin
      ListCopie:=TList.Create;
      for i:=0 to ListNoeud.count-1 do
        begin
        add(Integer(ListNoeud[i]));
        Listcopie.Clear;
        for j:=0 to ListNoeud.count-1 do
          Listcopie.Add(Pointer(Integer(ListNoeud[j])));
        Listcopie.Delete(i);
        Arbre(ListFils[i]).Permutation(Listcopie);
        end;
      ListCopie.Free;
    end;
     
     
     
    end.

  8. #8
    Expert éminent sénior
    Avatar de Guigui_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2002
    Messages
    1 864
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2002
    Messages : 1 864
    Points : 10 067
    Points
    10 067
    Par défaut
    je viens enfin de reussir a les recuperer (sous forme de liste)

    dans la classe arbre, il faut ajouter ses deux fonctions

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    procedure Arbre.Supprimerdernierelement();
    begin
        if &#40;Arbre&#40;Listfils&#91;0&#93;&#41;.listfils.count<>0&#41; then
          begin
          Arbre&#40;listfils&#91;0&#93;&#41;.Supprimerdernierelement&#40;&#41;;
          end
          else
          begin
          Listfils.Delete&#40;0&#41;;
          end;
      end;
    end;
     
    procedure Arbre.Supprimerautre&#40;indexmax,index&#58;Integer;aa&#58;Arbre&#41;;
    begin
          if &#40;indexmax<>index&#41; and &#40;Arbre&#40;Listfils&#91;0&#93;&#41;.listfils.count=0&#41;  then
          begin
          aa.Supprimerdernierelement&#40;&#41;;
          aa.Supprimerautre&#40;indexmax,0,aa&#41;;
          exit;
          end ;
          if indexmax>index then Arbre&#40;listfils&#91;0&#93;&#41;.Supprimerautre&#40;indexmax,index+1,aa&#41;;
    end;

    et voila un exemple avec 5 elements
    il faut un memo et un bouton sur ta forme
    Ca marche nickel sauf que il manque un element (celui correspondant à la liste à l'invers)
    normalement, il y a 120 valeurs (mais si dans le for, je met 119, ca plante)



    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    procedure TForm1.Button1Click&#40;Sender&#58; TObject&#41;;
    var
      l&#58;TList;
      ll&#58;TList;
      i,j&#58;integer;
    begin
      l&#58;=TList.Create;
      ll&#58;=TList.Create;
      l.Add&#40;Pointer&#40;1&#41;&#41;;
      l.Add&#40;Pointer&#40;2&#41;&#41;;
      l.Add&#40;Pointer&#40;3&#41;&#41;;
      l.Add&#40;Pointer&#40;4&#41;&#41;;
      l.Add&#40;Pointer&#40;5&#41;&#41;;
      MonArbre.Permutation&#40;l&#41;;
      for i&#58;=0 to 118 do
        begin
        ll.Clear;
        Arbre&#40;MonArbre.listfils&#91;0&#93;&#41;.ConsitueListe&#40;ll&#41;;
        MonArbre.supprimerdernierelement&#40;&#41;;
        MonArbre.Supprimerautre&#40;4,0,MonArbre&#41;;
    // la valeur 4 correspond à p-1
          for j&#58;=0 to 4 do
            Memo1.Text&#58;=Memo1.Text+inttostr&#40;Integer&#40;ll&#91;j&#93;&#41;&#41;+ '  ';
          Memo1.Text&#58;=Memo1.Text+chr&#40;13&#41;+chr&#40;10&#41;;
    end;
    end;
    Pour resumé,
    tu recupères avec ton prog sur les Cnp les différentes combinaisons possibles. Puis pour chaque combinaison, tu peux appliquer mon algo qi permet de trouver toutes les permutations possibles d'une liste de p éléments.


    si tu veux plus d'explication ou si tu ne connais pas delphi, dis-le moi, j'essaierai d'expliquer l'algo plus clairement

    ouf, j'ai enfin fini, je vais pouvoir aller manger

  9. #9
    Expert éminent sénior
    Avatar de Guigui_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2002
    Messages
    1 864
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2002
    Messages : 1 864
    Points : 10 067
    Points
    10 067
    Par défaut
    j'ai trouvé une améliorations qui permet directement de calculer les Anp (sans avoir besoin de passer par les cnp)

    en fait, au lieu de créer l'arbre des permutations (de hauteur n), il suffit de créer cet arbre avec une hauteur p.

    Donc il faut modifier la fonction permutation de la classe arbre pour ne construire qu'un arbre de taille p.

    Ca marche nickel (y'a toujours le problème qu'il me manque un élément à la restitution), c'est pas gênant en soi.
    J'ai maintenant une belle appli qui m'affiche les Anp.

    Au passage, je viens de compléter mon appli pour quelle fasse aussi l'énumération des Cnp (mon algo se base aussi sur l'exploitation d'un arbre (il suffit juste de ne pas le remplir de la même façon).

    Si tu pouvais expliquer ton algo pour les Cnp, ça m'intéresse pour comparer avec ma méthode

  10. #10
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2003
    Messages
    52
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2003
    Messages : 52
    Points : 75
    Points
    75
    Par défaut
    Si la récursivité ne vous fait pas peur... Le code suivant semble fonctionner

    Pour les combinaisons, le premier appel se fait par Cnp(5, 3, liste vide)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    procedure Cnp&#40;n, p, liste&#41;
     
       si p = 0 alors
          begin     
          affiche liste
          fin de la procedure
          end
     
        si n = 0 alors fin de la procedure
     
        cnp&#40;n-1,  p-1,  liste + &#123;élément numéro n&#125;&#41;
        cnp&#40;n-1,  p,    liste&#41;


    Pour les arrangements, l'appel se fait par Anp(5, 3, liste vide)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    procedure anp&#40;n, p, liste&#41;
     
        variable k &#58; entier
     
        si p = 0 alors
           begin
           affiche chaine
           on sort de la procedure
           end
     
        pour k valant 1 à n faire
               si la liste ne contient pas l'élément numéro k 
              alors anp&#40;n, p-1, liste + &#123;élément numéro k&#125;&#41;;

    La liste peut être une chaine à laquelle on ajoute le caractère de code 64+i (pour le i-ème élément)

  11. #11
    Expert éminent sénior
    Avatar de Guigui_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2002
    Messages
    1 864
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2002
    Messages : 1 864
    Points : 10 067
    Points
    10 067
    Par défaut
    pas mal
    c'est beaucoup plus efficace que ce que je propose.

  12. #12
    Membre éclairé

    Homme Profil pro
    Fondateur de ZetaPush - realtime BaaS
    Inscrit en
    Mars 2002
    Messages
    146
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Fondateur de ZetaPush - realtime BaaS
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mars 2002
    Messages : 146
    Points : 687
    Points
    687
    Par défaut
    Bonjour,

    Je viens d'arriver au boulot et je trouve tout ça sur le forum
    C'est vraiment magnifique

    Merci beaucoup, je test immédiatement et je vous tiens au courant.

    Merci encore,
    Mikaël Morvan
    ZetaPush: realtime BaaS www.zetapush.com

  13. #13
    Membre éclairé

    Homme Profil pro
    Fondateur de ZetaPush - realtime BaaS
    Inscrit en
    Mars 2002
    Messages
    146
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Fondateur de ZetaPush - realtime BaaS
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mars 2002
    Messages : 146
    Points : 687
    Points
    687
    Par défaut [Résolu] trouver l'arrangement de n éléments parmis p (Anp)
    Voila, j'ai testé et ça marche

    Le code en Delphi:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    procedure TForm1.Anp&#40;n, p&#58; Integer; chaine&#58; string&#41;;
    var
      k&#58; Integer;
    begin
      if p= 0 then
      begin
        Liste.Add&#40;chaine&#41;;
        exit;
      end;
     
      for k&#58;= 1 to n do
        if pos&#40; Chr&#40;64+k&#41;, chaine&#41;= 0 then
          Anp&#40;n, p-1, chaine + Chr&#40;64+k&#41;&#41;;
    Ce code permet de faire l'arrangemen des différentes lettres de l'alphabet.
    Ma liste est une TStringList que j'assigne à un TMemo pour l'affichage final.

    Pour les personnes qui ne connaissent pas Delphi, la fonction pos retourne 0 si la sous-chaine n'a pas été trouvée dans la chaine principale.

    Voila, merci beaucoup à Diedie et siocnarf pour leur aide.
    ZetaPush: realtime BaaS www.zetapush.com

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

Discussions similaires

  1. [Algo] Trouver un arrangement ou une combinaison d'éléments
    Par Morvan Mikael dans le forum Algorithmes et structures de données
    Réponses: 16
    Dernier message: 20/04/2013, 12h46
  2. Taille d'un Enuméré...
    Par kris1980 dans le forum C++
    Réponses: 9
    Dernier message: 30/07/2009, 12h46
  3. Recherche des arrangements
    Par lper dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 09/11/2004, 11h35
  4. [TListView] Déplacer / Arranger les items
    Par Ingham dans le forum Composants VCL
    Réponses: 4
    Dernier message: 14/07/2004, 16h52
  5. [Algo] Permutations et arrangements
    Par rbag dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 13/10/2003, 12h40

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