Discussion :

[Mohammed_S]

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

[Nebulix]

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

[cs_ntd]

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

[Mohammed_S]

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

[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 :

Code java :

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
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".

[Mohammed_S]

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

[Acrim]

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

Code :

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

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 :

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

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