Combinaison avec répétition et ordre

Version imprimable

18/04/2012, 17h57
maxha

Combinaison avec répétition et ordre

Bonjour,

Je cherche à entrer dans un tableau toutes les combinaisons possibles de n caractères parmi les 4 suivants (A, B, C, D), avec répétition et en tenant compte de l'ordre.

Merci d'avance pour votre aide.
18/04/2012, 17h59
dinobogan

Quel est le problème ?
18/04/2012, 18h01
maxha

Je ne trouve pas d'algorithme fonctionnant
19/04/2012, 11h05
hwoarang

Un moyen pas trop compliqué serait d'utiliser un algo recursif...

Bonjour,

J'ai du mal a bien comprendre la récursivité,
Voici le code dernier code que j'ai écris mais lorsque n est supérieur à 2 le code ne fonctionne pas.

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Test 
{
	static int n = 3 ;
	static int puissance= (int) Math.pow(4, n);
	static String t1[] = new String[puissance];	
	static String[] choix = {"A","B","C","D"}; 
 
	public static void main(String[] args) 
	{		
 
		combi(choix);		
 
		for(int i=0;i<t1.length;i++)
		{
			System.out.println(t1[i]);
		}			
 
	}
 
    public static void combi(String[] tab)
    {
    	String[] tab2 = {"A","B","C","D"};
    	int x = 0;
 
    	for(int i=0;i<tab.length;i++)
    	{
    		for(int j=0;j<tab2.length;j++)
        	{    			    			
    			t1[x]=tab[i]+tab2[j];
    			x++;
        	}
    	}	
 
    	for(int i=0;i<n-2;i++)
    	{
    		combi(t1);
    	}
    }
}

Bonjour maxha,

Ton problème vient du fait que tu calcules une taille de tableau. Hors celle-ci est insuffisante pour stocker toutes les possibilités. Le mieux est d'utiliser les listes (List pour l'interface et ensuite prendre une implémentation par exemple ArrayList). Les tailles ne sont pas figées.

Pour t'expliquer l'algorithme, je suis pas très doué. Je viens de l'implémenter (même si c'est surement perfectible). Si tu as besoin d'explication, n'hésite pas à demander.

Pour information, passé 10 ça commence à être assez long.
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 25 26 27 28 29 30 31 32 33 34 35 36 package net.developpez.java; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class CombinaisonChaine { static final int nbLettre = 5; static String[] choix = { "A", "B", "C", "D" }; public static void main(String[] args) { List<String> listeString = combi(Arrays.asList(choix)); for (String string : listeString) { System.out.println(string); } } public static List<String> combi(final List<String> listeString) { List<String> nouvelleListeString = new ArrayList<String>(); for (String stringReference : choix) { for (String string : listeString) { if (string.length() == nbLettre) { return listeString; } nouvelleListeString.add(stringReference + string); } } return combi(nouvelleListeString); } }

Citation:

Envoyé par maxha

J'ai du mal a bien comprendre la récursivité,
Voici le code dernier code que j'ai écris mais lorsque n est supérieur à 2 le code ne fonctionne pas.

Un methode recursive est une methode qui s'appelle elle-meme. Il faut donc lui donner une condition d'arret sans quoi elle boucle a l'infini (ce qui est le cas dans ton code quand n>2).

De plus, le remplissage de tl est incorrect. Tu boucles sur tab.length puis tab2.length. Or, comme tu l'as créé, sa taille n'est pas de 4 x 4 mais de 4^n. Le plus simple pour faire marcher ton code est de passer en parametre la profondeur. Essaye en ajoutant la profondeur dans ta procédure.

Ca donnera un truc du genre :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 public static void combi(String[] tab, int profondeur) { // Traitement if(prof > 0) { combi(tab, profondeur - 1); } else { // c'est fini } }

20/04/2012, 16h57
maxha

Ok
effectivement j'ai effectué les modifications et cela fonctionne

Merci pour votre aide !