Discussion :

[akrogames]

Bonjour à tous,

J'ai pu voir que je n'étais pas le seul avec un problème de combinaison à répétition à résoudre. Mais aucune réponse ne m'a donné entière satisfaction. Ainsi je me permet de poster afin que l'on puisse en discuter.

S'agissant d'un problème dans un métier très spécifique, je me permet de faire de la régression de langage en présentant le problème grâce à des sacs de billes et des billes.

En effet, je souhaites lister toutes les combinaisons possibles me permettant de ranger toutes les billes dans les sacs.

B = Une bille
S = un sac de bille

La contenance de S est de 0 à B[].size. Dans mon problème on a 3 sacs de billes et 5 billes à placer. Les sacs sont donc des ensembles pouvant contenir les billes. Le problème c'est déjà dans le calcul des solutions possible :
int nbcombiposs = fact(n + k - 1) / (fact(k) * fact(n-1));
Cela me donne 21 car on ne peut mettre qu'une bille dans un sac, du coup, cela ne répond pas au problème.

Viens ensuite le problème avec des boucles itératives, mais là encore je sèche, je n'obtiens que les solutions de base...

Voilà le résultats que je souhaiterais obtenir :
S1:{B1,B2,B3,B4,B5},S2:{},S3:{}
S1:{},S2:{B1,B2,B3,B4,B5},S3:{}
S1:{},S2:{},S3:{B1,B2,B3,B4,B5}
S1:{B1},S2:{B2,B3,B4,B5},S3:{}
S1:{B2},S2:{B1,B3,B4,B5},S3:{}
etc...
et ainsi de suite jusqu'à parcourir toutes les solutions. J'ai bien penser à des méthodes de backtracking et d'exploration d'arbres, mais du coup je suis perdu dans mes recherches.

C'est pourquoi je soumet la problématique aux idées.

D'avance merci.

[mehdidc]

Bonjour à tous,

J'ai pu voir que je n'étais pas le seul avec un problème de combinaison à répétition à résoudre. Mais aucune réponse ne m'a donné entière satisfaction. Ainsi je me permet de poster afin que l'on puisse en discuter.

S'agissant d'un problème dans un métier très spécifique, je me permet de faire de la régression de langage en présentant le problème grâce à des sacs de billes et des billes.

En effet, je souhaites lister toutes les combinaisons possibles me permettant de ranger toutes les billes dans les sacs.

B = Une bille
S = un sac de bille

La contenance de S est de 0 à B[].size. Dans mon problème on a 3 sacs de billes et 5 billes à placer. Les sacs sont donc des ensembles pouvant contenir les billes. Le problème c'est déjà dans le calcul des solutions possible :
int nbcombiposs = fact(n + k - 1) / (fact(k) * fact(n-1));
Cela me donne 21 car on ne peut mettre qu'une bille dans un sac, du coup, cela ne répond pas au problème.

Viens ensuite le problème avec des boucles itératives, mais là encore je sèche, je n'obtiens que les solutions de base...

Voilà le résultats que je souhaiterais obtenir :
S1:{B1,B2,B3,B4,B5},S2:{},S3:{}
S1:{},S2:{B1,B2,B3,B4,B5},S3:{}
S1:{},S2:{},S3:{B1,B2,B3,B4,B5}
S1:{B1},S2:{B2,B3,B4,B5},S3:{}
S1:{B2},S2:{B1,B3,B4,B5},S3:{}
etc...
et ainsi de suite jusqu'à parcourir toutes les solutions. J'ai bien penser à des méthodes de backtracking et d'exploration d'arbres, mais du coup je suis perdu dans mes recherches.

C'est pourquoi je soumet la problématique aux idées.

D'avance merci.

Bonjour,

pour le calcul du nombre de combinaisons possibles, je pense que c'est 3^5:
On place chaque boule dans un ensemble, donc on a 3 possibilités pou chaque boule.

Pour l'algorithme permettant de lister les combinaisons possibles je pense à quelque chose du genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
CombinaisonsPossibles(S[1..3], boule):
   si boule > 5:
       afficher S
   sinon:
      pour i allant de 1 à 3:
         ajouter  boule à S[i]
         CombinaisonsPossibles(S, boule + 1) 
         retirer boule à S[i]