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.
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.
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.
Il existe bien sûr d'autres algos.
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 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
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.
Tu ne peux pas... En effet le nombre de combinaison de p parmi n croît déjà plus vite que O(np) !Envoyé par marocleverness
--
Jedaï
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)).
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager