Algorithme combinaison denombrement

Bonjour tout le monde , je sais pas ce que c'est ce que je demande vraiment et c'est pour ça que j'ai mis ce titre un peu ambigu .

j'ai une liste (ligne d'une matrice par exemple ) composée de N cases dans lesquelles j'ai K fois le nombre 1 et N-K fois le nombre 0 :)
je cherche un algorithme qui me permet d'avoir toutes les combinaisons possibles .


j'ai imaginé un algo récursif avec une pile mais je n'arrive vraiment pas à le concevoir :)

merci d'avance

Tous les nombres de 0 à N écrits en binaire ?

Je pense que tu peux le faire avec k boucles imbriquées, ici l'exemple avec 3 :

Code:

---

1 2 3 4 5 6 7 8

for(i=0; i <N-2; i++) { for(j=i+1; i<N-1; j++) { for(k=j+1; k < N; k++) { //Mettre les case i,j et k à 1 } } }

---

D'où un truc du genre :

Code:

---

1 2 3 4 5 6 7 8 9

boucle(K, debut, N, L) { if(K>0) { for(i=debut, i<N-K, i++) boucle(K-1,i+1, N, L union {i}) } else { // Resultat L } }

---

avec comme appel : boucle(K,0,N,{})

• K : le nombre de 1 à insérer
• N : le nombre d’éléments
• L : l'ensemble contenant les index des cases à mettre à 1

Citation:

---

Envoyé par Nebulix

Tous les nombres de 0 à N écrits en binaire ?

---

Il me semble oui... En gors Ya que des 0 et des 1, et pas d'ordre specifique ?

Un peu compliqué ton systeme Acrim... surtout les K boucles :?

Merci pour vos réponses :)
ce ne sont pas tous les nombres binaires car le nombre des 1 est fixe , cependant ça m'a donné l'idée de générer tous les nombres binaires et d'en retenir ceux que je veux :)

@Acrim

je pense qu'il y a toujours le problème de l'initialisation de la liste (L) à chaque fois , même si j'ai pas bien compris ton algo peut être :)

Tous les nombres binaires, ça en fait quand même 2^N pour une nombre de combinaisons "gagnantes" pas forcement élevé (tirage de k éléments dans un ensemble en comportant N aux permutations prés, ce qui doit faire n!/(n-k)!k!) :)

Par rapport à mon algo., le seul appel que tu as à faire serait : boucle(K,0,N,{}).
L contenant une combinaison possible chaque fois que la ligne 6 est atteinte.

Une implémentation vite fait :

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

public class Combinaison { public static void main(String[] args) { int nbUn = 7; int nbElements = 20; iniBoucle(nbUn, nbElements); }   public static void iniBoucle(int k, int n) { boucle(k,0,n, new BitSet()); }   public static void boucle(int k, int debut, int n, BitSet idxs) { if(k > 0) { for(int i = debut; i < n; i++) { idxs.set(i); boucle(k-1, i+1, n, idxs); idxs.clear(i); } } else { System.out.println(idxs); } } }

---

ps : Une autre réponse plus maline pour la gestion de "L".

Citation:

---

Envoyé par Acrim

Tous les nombres binaires, ça en fait quand même 2^N pour une nombre de combinaisons "gagnantes" pas forcement élevé (tirage de k éléments dans un ensemble en comportant N aux permutations prés, ce qui doit faire n!/(n-k)!k!) :)

Par rapport à mon algo., le seul appel que tu as à faire serait : boucle(K,0,N,{}).
L contenant une combinaison possible chaque fois que la ligne 6 est atteinte.

Une implémentation vite fait :
.

---

merciii Acrim ça marche comme dans un rêve :)
ça m'a permis aussi de découvrir BitSet ;)

je trouve aussi que ta gestion de la liste est plus maline et propre