Enumération de l'arrangement Anp

Version imprimable

25/04/2003, 16h50
Morvan Mikael

[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
25/04/2003, 17h00
Morvan Mikael

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 :lol: :lol:
25/04/2003, 17h04
Guigui_

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)
25/04/2003, 17h48
Guigui_

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
25/04/2003, 19h36
delphi-fan

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+
26/04/2003, 11h49
Guigui_
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:

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)

voilà un prog qui permet de créer l'arbre des permutations
je l'ai fait en delphi

prog principale :

Code:

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:

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.

je viens enfin de reussir a les recuperer (sous forme de liste)

dans la classe arbre, il faut ajouter ses deux fonctions
Code:

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 (Arbre(Listfils[0]).listfils.count<>0) then begin Arbre(listfils[0]).Supprimerdernierelement(); end else begin Listfils.Delete(0); end; end; end; procedure Arbre.Supprimerautre(indexmax,index:Integer;aa:Arbre); begin if (indexmax<>index) and (Arbre(Listfils[0]).listfils.count=0) then begin aa.Supprimerdernierelement(); aa.Supprimerautre(indexmax,0,aa); exit; end ; if indexmax>index then Arbre(listfils[0]).Supprimerautre(indexmax,index+1,aa); 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:

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(Sender: TObject); var l:TList; ll:TList; i,j:integer; begin l:=TList.Create; ll:=TList.Create; l.Add(Pointer(1)); l.Add(Pointer(2)); l.Add(Pointer(3)); l.Add(Pointer(4)); l.Add(Pointer(5)); MonArbre.Permutation(l); for i:=0 to 118 do begin ll.Clear; Arbre(MonArbre.listfils[0]).ConsitueListe(ll); MonArbre.supprimerdernierelement(); MonArbre.Supprimerautre(4,0,MonArbre); // la valeur 4 correspond à p-1 for j:=0 to 4 do Memo1.Text:=Memo1.Text+inttostr(Integer(ll[j]))+ ' '; Memo1.Text:=Memo1.Text+chr(13)+chr(10); 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 :wink:

27/04/2003, 18h43
Guigui_

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

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:

1
2
3
4
5
6
7
8
9
10
11
12
procedure Cnp(n, p, liste)
 
   si p = 0 alors
      begin     
      affiche liste
      fin de la procedure
      end
 
    si n = 0 alors fin de la procedure
 
    cnp(n-1,  p-1,  liste + {élément numéro n})
    cnp(n-1,  p,    liste)

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

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
procedure anp(n, p, liste)
 
    variable k : 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(n, p-1, liste + {élément numéro k});

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

28/04/2003, 08h11
Guigui_

pas mal
c'est beaucoup plus efficace que ce que je propose.
28/04/2003, 08h38
Morvan Mikael

Bonjour,

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

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

Merci encore,
Mikaël Morvan

[Résolu] trouver l'arrangement de n éléments parmis p (Anp)

Voila, j'ai testé et ça marche :lol:

Le code en Delphi:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 procedure TForm1.Anp(n, p: Integer; chaine: string); var k: Integer; begin if p= 0 then begin Liste.Add(chaine); exit; end; for k:= 1 to n do if pos( Chr(64+k), chaine)= 0 then Anp(n, p-1, chaine + Chr(64+k));
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.