Discussion :

[Flaburgan]

Bonjour à tous

Je poste en Java parce que je code pour l'instant en Java, mais c'est en fait une question d'algo.

J'ai une série d'objet, et je souhaite tous les énumérer sans relation d'ordre :

{a,b,c}

0
a
b
c
ab
ac
cb
abc

On est donc en 2^n
Je peux éventuellement connaître le n.
Comment faire ça ?

[Rei Ichido]

Tu pars d'une List<Set<String>>, qui commence avec un élément : un set vide.
Tu itères sur les éléments de ton set de départ, puis sur les Sets de ta liste. Au sein de cette itération, pour chaque Set, tu le copies et tu rajoutes l'élément en cours, et tu le colles dans une liste de set, que tu ajouteras à la fin de l'itération sur l'élément.

Edit : quelque chose du genre :

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
 
	public static List<Set<String>> combinaisons(Set<String> elements) {
		List<Set<String>> listeCombinaisons = new LinkedList<Set<String>>();
		Set<String> elementVide = new HashSet<String>();
		listeCombinaisons.add(elementVide);
 
		for (String element : elements) {
			List<Set<String>> listeNouvellesCombinaisons = new LinkedList<Set<String>>();
			for (Set<String> set : listeCombinaisons) {
				Set<String> nouvelleCombinaison = new HashSet<String>(set);
				nouvelleCombinaison.add(element);
				listeNouvellesCombinaisons.add(nouvelleCombinaison);
			}
			listeCombinaisons.addAll(listeNouvellesCombinaisons);
		}
		return listeCombinaisons;
	}

[+Guilhem]

Tu pars d'une List<Set<String>>, qui commence avec un élément : un set vide.
Tu itères sur les éléments de ton set de départ, puis sur les Sets de ta liste. Au sein de cette itération, pour chaque Set, tu le copies et tu rajoutes l'élément en cours, et tu le colles dans une liste de set, que tu ajouteras à la fin de l'itération sur l'élément.

Edit : quelque chose du genre :

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
 
	public static List<Set<String>> combinaisons(Set<String> elements) {
		List<Set<String>> listeCombinaisons = new LinkedList<Set<String>>();
		Set<String> elementVide = new HashSet<String>();
		listeCombinaisons.add(elementVide);
 
		for (String element : elements) {
			List<Set<String>> listeNouvellesCombinaisons = new LinkedList<Set<String>>();
			for (Set<String> set : listeCombinaisons) {
				Set<String> nouvelleCombinaison = new HashSet<String>(set);
				nouvelleCombinaison.add(element);
				listeNouvellesCombinaisons.add(nouvelleCombinaison);
			}
			listeCombinaisons.addAll(listeNouvellesCombinaisons);
		}
		return listeCombinaisons;
	}

Et avec une quinzaine d'éléments on peut aller prendre un café avant le résultat.

[Rei Ichido]

15 ça passe encore pas trop mal chez moi, mais faut pas aller chercher beaucoup plus loin, vers 20 ça devient vraiment très long.
En même temps, générer 2^20 sets ...

[Flaburgan]

Ce sont des entiers, le but était en fait de résoudre le problème de partition, donc j'ai fait ça en récursif avec un tableau, je suis encore autour des 4 secondes pour 25 éléments, par contre je passe à 80 secondes pour 30 éléments.

[semaesma]

Bonjour,

Cela fait un bon moment que j'essaie de trouver une réponse à mon problème mais rien à faire. Je me permet de s’adresser à vous pour une aide.
J'ai un ensemble de nombre E ={1,2,3,4} et je veux avoir toutes les solutions permettant de diviser E en sous ensembles.

Par exemple pour 3 nombres les sous ensembles sont:
{1,2,3}
{1}, {2,3}
{1,2},{3}
{1,3},{2}
{1},{2},{3}
Pour 4 nombre c'est plus compliqué car on peut avoir plus de deux sous ensemble on a 3 sous ensembles pour chaque solution:
par exemple:
{1,2},{3,4}
{1,2},{3},{4}
{1},{2},{3,4}

Quelqu'un a une idée sur comment faire la récursion ?

[Beginner.]

Bonjour,

Énumérer les combinaisons, il fallait aussi que je fasse ce genre de chose dans ce code en java ici : #10...

Est-ce que dans ton cas aussi le nombre d'objets est variable ? Que sont ces objets (car je suppose que ce ne sont pas des lettres de l'alphabet) ?

...