Discussion :

[chekchouka]

Bonjour à tous,

J'ai un ensemble de n objets et je veux récupérer toute les combinaisons possibles de p éléments parmi ces n...
Si j'ai [ 1 2 3 ]
avec p=2 je veux [ 1 2 ] [ 1 3 ] [ 2 3 ]
par contre [ 2 1 ] c'est la même chose que [ 1 2 ] donc il faut que je récupère seulement l'un des deux.

Voila mon problème, j'y ai longuement réfléchi mais j'ai vraiment beaucoup de mal à mettre ça sous forme de code.

Si quelqu'un peut m'aider....

[michon]

Mettre sous forme de code est simple...

Le plus dure est ici de mettre cela sous forme mathématique. Une fois que tu auras tes formules mathématiques bien écrites, la rédaction du code en lui même sera très aisé car de souvenir, cela ne nécessite en plus aucune opération mathématique complexe.

Après à voir si il n'existerait pas des frameworks développés spécialement pour les statistiques... cela pourrai être un plus.

[professeur shadoko]

bien étudier les objectifs du code, j'ai dans mes projets privés quelque chose qui fait ça et regardes bien l'API

Code :

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

1
2
3
 
public Combineur(T[] données, int nbElem) {.....}
 public Iterator<T[]> iterator() {....}

le truc c'est que ce code ne gaspille pas de mémoire: chaque combinaison est allouée et calculée sur chaque appel du next() de l'Iterateur.
Je l'ai utilisé pour des nombres de combinaisons faramineux.

[chekchouka]

Merci vous deux.

@michon : mathématiquement ça me parait très clair, je sais qu'il y'a n!/( (n-p)!*p! ) solutions, je sais que ça représente tous les ensembles distincts (l'ordre n'a pas d'importance) de p éléments parmi n...
Par contre mon problème est de traduire en algorithme quelque chose qui se fait à la main naturellement mais qui est beaucoup moins naturel pour moi à informatiser.

@professeur shadok : je ne trouve pas l' API que tu mentionnes, as-tu des liens?

[chekchouka]

Alors voilà ce que j'ai essayé de faire en récursif mais qui fonctionne pas :

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
18
public static ArrayList<ArrayList<Integer>> combinaison(ArrayList<Integer> liste, int p){
	ArrayList<ArrayList<Integer>> combinaisons = null;
	if (p==0 || liste.size()<p){
		//ne rien faire -> condition d'arret
	}
	else{
		for(int i=0;i<liste.size();i++){
			int elt = liste.get(i);
			liste.remove(i);
			ArrayList<ArrayList<Integer>> combinaisonsReste = combinaison(liste, p-1);
			for(int j=0; j<combinaisonsReste.size();j++){
				combinaisonsReste.get(j).add(0, elt);
				combinaisons.add(combinaisonsReste.get(j));
			}
		}
	}
	return combinaisons;
}

Je suis complètement à coté de la plaque, ou je chauffe ??

[professeur shadoko]

@professeur shadok : je ne trouve pas l' API que tu mentionnes, as-tu des liens?

normal j'ai dit: "dans mes projets privés"
j'incitais dans mon post à réfléchir à un algorithme qui crée chaque combinaison au fur et à mesure de la demande: on trouve sur le web des tas de solutions qui créent un énorme tableau à deux dimensions .

[hlbnet]

Proposition:

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package com.ibm.pdp.util.test;
 
import java.util.Arrays;
 
public class AnyTest
{
	public static void main( String[] args )
	{
		String[] tokens = { "Hello", "wonderful", "giant", "world", "leader", "!!!" };
 
		int count = 3;
		Combiner<String> combiner = new Combiner<String>( count, tokens );
		String[] result = new String[count];
		while ( combiner.searchNext( result ) )
			System.out.println( Arrays.toString( result ) );
	}
 
	public static class Combiner<T>
	{
		protected int count;
		protected T[] array;
		protected int[] indexes;
 
		public Combiner( int count, T[] array )
		{
			super();
			this.count = count;
			this.array = array;
			indexes = new int[count];
			for ( int i = 0; i < count; i++ )
				indexes[i] = i;
		}
 
		public boolean searchNext( T[] result )
		{
			if ( indexes == null )
				return false;
 
			int resultIndex = 0;
			for ( int index : indexes )
				result[resultIndex++] = array[index];
 
			int indexesRank = count-1;
			int arrayRank = array.length-1;
			while ( indexes[indexesRank] == arrayRank )
			{
				if ( indexesRank == 0 )
				{
					indexes = null;
					return true;
				}
				indexesRank--;
				arrayRank--;
			}
 
			int restartIndex = indexes[indexesRank] + 1;
			while ( indexesRank < count )
				indexes[indexesRank++] = restartIndex++;
 
			return true;
		}
	}
}