toutes les combinaisons possibles

Version imprimable

28/05/2006, 18h19
marocleverness

toutes les combinaisons possibles

Bonjour

Comment peut je obtenir tous les combinaisons de p éléménts parmi n élement (p<n bien sur) en un temps O(n.p)?

Merci d'avance pour vos réponses.
28/05/2006, 18h52
marocleverness

j'ai pensé à faire une récursion un peu cacher.

on considerons une bijection de l'ensemble de mes elements dans [1,n].

je vais diviser mes combinaisons de p element parmi n element en sous classes.

deux combinaisons a_1,a_2,...,a_p et b_1,b_2,...,b_p appartiennenet à la même classe ssi a_{i+1}-a_i=b_{i+1}-b_i
donc si on trouve un seul élémént de la classe on déduit les autres.

et on remarque que le fait de détérminer une classe revient à choisir une combinaison de p-1 éléments de [1,x] de x élement avec :
x=E(n-1/(p-1)+(p-1)/2).

donc on descent à p-1 .

Mais le probléme c'est je sais pas calculer sa complexité.

Merci de vos aides

Une possibilité est d'utiliser des files. L'algo est très simple:

Les élements de la file sont constitués d'un tableau de p élements et du nombre n d'éléments déjà insérés.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
début
  // initialisation de la file
  on insère dans la file un élément vide
  tant que la file n'est pas vide faire
    extraire le premier élément ef de la file
    pour tous les éléments elem du tableau intial "supérieurs" au denier élément inséré faire
      créer un nouvel élément efn à partir de l'ancien ef
      ajouter en fin lde tableau de efn l'élément elem
      incrémenter le nombre d'éléments de efn
      si le nombre d'éléments de efn est égal à p alors
        ecrie la permutation obtenue
      sinon
         insérer efn en fin de file
      fin si
    fin pour
  fin tant que
fin

Il existe bien sûr d'autres algos.

28/05/2006, 19h12
marocleverness

Désolé, mais j'ai rien zapé
28/05/2006, 21h10
Trap D

Oh, c'est tout simple :

Suppose que tu veuilles obtenir toutes les combinaisons de 3 nombres pris parmi 5 (on suppose que l'ordre n'a pas d'importance 1 2 3 ou 1 3 2 sont identiques.

l'élément à mettre dans la file est une structure du type ([X,X,X] , 0), tableau et nombre d'éléments mis.

Tu initialises avec ([0, 0, 0], 0)

tu extrais ([0, 0, 0], 0)

comme il n'y a pas de nombre mis
tu créées ([1,0,0], 1) que tu mets dans la file
tu créées ([2,0,0], 1) que tu mets dans la file
tu créées ([3,0,0], 1) que tu mets dans la file
tu créées ([4,0,0], 1) que tu mets dans la file
tu créées ([5,0,0], 1) que tu mets dans la file

tu extrais ([1,0,0], 1) de la file
tu créées ([1,2,0], 2) que tu mets dans la file
tu créées ([1,3,0], 2) que tu mets dans la file
tu créées ([1,4,0], 2) que tu mets dans la file
tu créées ([1,5,0], 2) que tu mets dans la file

tu extrais ([2,0,0], 1) de la file
tu créées ([2,3,0], 2) que tu mets dans la file
tu créées ([2,4,0], 2) que tu mets dans la file
tu créées ([2,5,0], 2) que tu mets dans la file

tu extrais ([3,0,0], 1) de la file
tu créées ([3,4,0], 2) que tu mets dans la file
tu créées ([3,5,0], 2) que tu mets dans la file

tu extrais ([4,0,0], 1) de la file
tu créées ([4,5,0], 2) que tu mets dans la file

tu extrais ([5,0,0], 1) de la file
tu ne peux rien faire

etc...

Si l'ordre à une importance, au lieu de mettre les nombres plus grands, on ajoute les nombres différents de ceux déjà mis.
28/05/2006, 21h46
Jedai

Citation:

Envoyé par marocleverness

Bonjour

Comment peut je obtenir tous les combinaisons de p éléménts parmi n élement (p<n bien sur) en un temps O(n.p)?

Merci d'avance pour vos réponses.

Tu ne peux pas... En effet le nombre de combinaison de p parmi n croît déjà plus vite que O(np) !

--
Jedaï
29/05/2006, 00h11
marocleverness

Merci TrapD j'ai compris à travers l'exemple.j'ai pas pensé à cette méthode.

Désolé je voulais dire en O(C(p,n)).
sinon je pense que cet algorithme est en O(p.C(p,n)).