Discussion :

[lalalala75]

Bonjour,
J'aimerai avoir vos aides en ce qui concerne le problème suivant: soit un tableau de type string contenant des chaines de caractères, par exemple:

Code :

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

1
2
3
4
 
tab[0]="t1"
tab[1]="t2"
tab[2]="t3"

à partir de cette table, je veux obtenir toutes les combinaisons possibles ayant la forme suivante:

Code :

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

1
2
3
4
 
t1==>t2; t1==>t3; t2==>t1; t2==>t3; t3==>t1; t3==>t2; 
t1,t2==>t3; t1,t3==>t2; t2,t3==>t1; 
t1==>t2,t3; t2==>t1,t3; t3==>t1,t2

merci d'avance

[JoeChip]

Il faut chercher "algorithme de permutation"

[thierryler]

Il faut chercher "algorithme de permutation"

T'es fort, moi j'ai même pas compris la question. Et encore moins l’intérêt.

[lalalala75]

Bonjour, j'ai fait le programme java suivant qui permet de me donner les résultats ci-dessous:

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
public class Combin1 {
 
	public String[] init() {
		String mots[] = new String[3];
		mots[0] = "t1";
		mots[1] = "t2";
		mots[2] = "t3";
 
		return mots;
	}
 
	public int convertir_binaire(int x, int resultat[]) {
		int quotient, nb_bits = 0;
		int dividende = x;
 
		do {
			quotient = dividende / 2;
			resultat[nb_bits] = dividende - (2 * quotient);
			nb_bits++;
			dividende = quotient;
		} while (quotient > 0);
 
		return nb_bits;
	}
 
	void afficher_parties(int nb_elts, String[] m) {
		int i;
		int[] resultat = new int[8];
		for (int p = 0; p < 8; p++)
			resultat[p] = 0;
 
		int x = 0;
		int n = convertir_binaire(x, resultat);
		int compteur = 1;
 
		while (n <= nb_elts) {
 
			for (i = 0; i < n; i++)
 
				if (resultat[i] == 1)
					System.out.println(m[i]);
 
 
			System.out.println("\n");
			compteur++;
			x++;
			n = convertir_binaire(x, resultat);
		}
	}
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Combin1 c = new Combin1();
		String ma[] = c.init();
		int nb_elts = ma.length;
		c.afficher_parties(nb_elts, ma);
}
}

ce programme me fournit le résultat suivant:

t1


t2


t1
t2


t3


t1
t3


t2
t3


t1
t2
t3

Mes questions sont: comment je pourrai modifier dans mon programme de tel sorte à éliminer l'apparence des combinaisons d'ordre 1 à savoir: t1 tout seul, t2 tout seul ou t3 tout seul.
En plus comment je pourrai faire pour rajouter les autres combinaisons: puisque d'après ce programme j'obtiens par exemple "t1 t2" mais non pas l'inverse et ainsi de suite.
comment je pourrai mettre en jeux le signe ==> entre les différentes chaines de caractères? par exemple t1==>t2 , t2==>t1,....
merci d'avance.

[thierryler]

Par exemple, si on utilise "thierry Dupont garçon ", tu voudrais quoi ?

[lalalala75]

Bonjour,
et bien si l'on considère les trois chaines de caractères "thierry","Dupont" et "garçon ", on doit obtenir:3^d-2^(d+1)+1 où d est le nombre de termes (ici 3) donc ça nous fait 12 combinaisons qui sont:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
"thierry"==>"Dupont"
"thierry"==>"garçon "
"Dupont"==>"garçon "
"Dupont"==>"thierry"
"garçon "==>"Dupont"
"garçon "==>"thierry"
"thierry"==>"Dupont","garçon "
"Dupont"==>"thierry","garçon "
"garçon "==>"thierry","Dupont"
"thierry","Dupont"==>"garçon "
"thierry","garçon "==>"Dupont"
"garçon ","Dupont"==>"thierry"

Voilà ce que je veux comme résultat et je ne parviens pas à le faire correctement :/

[thierryler]

OK, donc, à partir d'un trio A, B, C, tu veux juste des combinaisons, le reste n'étant que de l'affichage.

Tu veux d'abord des combinaisons de deux :
AB AC BC (croissant)
CB CA BA (decroissant)

Puis les combinaisons de trois
ABC BAC BCA
ACB CAB CBA
BAC BCA

Mais là j'en ai déjà deux de plus que toi on dirait...

[lalalala75]

Bonsoir, en fait c'est pas obligé que ça soit un trio à partir de n'importe quel nombre de termes on doit être capable de générer les combinaisons possibles.
J'ai essayé un algorithme de permutation comme l'a indiqué JoeChip, basé sur la fonction factorielle, mais j'ai pu juste générer les combinaison d'une dimension fixe du genre, si j'ai 1, 2 et 3 j'aurai comme résultat:

Code :

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

1
2
3
4
5
6
123
132
213
231
312
321

ce qui donne un résultat incomplet :/
voici la classe que j'ai utilisé:

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
public class Permutation4 {
	 private int factorielle(int k){
		 int f=1;
	 for(int i=1;i<=k;i++)f=f*i;
	 return f;
	 } 
	 private void Permutation (int k,int [] r)
	    {
	        int fact = 1;
	        for (int i = 2 ;  i < r.length+1 ; i++)
	        {
	            fact = fact*(i-1);
	            int pos = i - ( (k/fact) % i ) - 1;
	            swap(pos,i-1,r);            
	        }
	    }
 
	    private void swap(int i, int j,int [] A)
	    {
	        int oi = A[i];
	        int oj = A[j];
	        A[j]=oi;
	        A[i]=oj;        
	    }
 
	    public void afficherpermutations(int [] v)
	    {
 
	        for (int i = 0 ; i < factorielle(v.length) ; i ++)
	        {
 
	             Permutation(i,v);
	             for(int j=0;j<v.length;j++)System.out.println(v[j]);System.out.println("\n");
	        }
	    }
public static void main(String[] args) {
	int v[]= {1,2,3,4};
	Permutation4 p4=new Permutation4();
	p4.afficherpermutations(v);
}
}

Un peu d'aide s'il vous plait

[thierryler]

Alors attend, je résume.

Tu as un nombre indéfini d'items. Ça peut être 3, 4, 5, .., N

Et en fait, tu veux toutes les combinaisons possibles qu'on peut faire avec les N items, sachant que les combinaisons doivent être constituées de 2 à N items.

Par exemple, si tu as A, B, C et D ça donnera des combinaisons du style

rang 2 : AB, AC, etc.
rang 3 : ABC, ABD, etc.
rang 4 : ABCD, ABDC, etc.

C'est bien ça ?

[lalalala75]

Bonjour, oui thierryler C'est exactement ça oui.

[thierryler]

OK, dans ce cas, je pense que le plus simple est de faire un algo récursif. Il va devoir gérer deux choses :
1) faire différentes tailles de combinaisons ;
2) faire toutes les combinaisons pour une taille donnée.

[lalalala75]

Vraiment l'idée semble très prometteuse...Est ce que vous pouvez m'orienter un peu plus??? vu que je travaille sur ça depuis un moment sans trouver un essor Merci beaucoup d'avance

[Adpar]

Bonjour,

Ce sujet devrait t'aiguiller, en particulier le deuxième message : Ici !

[lalalala75]

Bonjour, Merci Adpar pour le lien je vais le voir

[thierryler]

La partie la plus simple, c'est des combinaisons de différentes tailles.

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
 
String[] items = {"A", "B", ... , "Z"};
 
List<String[]> combinaisons = new ...
 
public void start() {
  for(int i = 2; i <= items.lenght; i++) {
    doCombinaisons(i, items);
  }
}
 
private void doCombinaison(int nb, String[] subitems) {
  ...
 
  combinaisons.add(..);
}