Nombre de Combinaisons possibles sans répétition

Version imprimable

Bonjour,
Je souhaite écrire une fonction récursive permettant de me fournir toutes les combinaisons possibles sans répétition.

Sans répétition c'est-à-dire si j'ai cette combinaison [1,2,3], je ne dois plus avoir celles là [1,3,2] && [3,1,2] && [2,3,1].

En utilisant ce code :

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
 
public class GreenTest 
{    
    static int n = 10;
    static int p = 3; 
    static boolean ordered = true;
    // liste construite par la recursion  
    static int[] liste = new int[p];
 
    // construction recursive des listes possibles
    public static void partition(int index) 
    {
        if(index >= p) 
        {
            // la liste est construite -> FIN 
            System.out.println(Arrays.toString(liste));
            return;
        }
 
        int start=1;
        if(ordered && index>0) 
        {
            start=liste[index-1]+1;
        }
 
        for(int i=start;i<n;i++) 
        {
            liste[index]=i;
            partition(index+1);
        }
    }
 
    public static void main(String[] args) 
    {
        partition(0);
    }
}

j'arrive à obtenir un résultat un peu similaire à mon besoin : Par exemple pour une combinaison avec deux chiffre allant de 1 à 9

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
 
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[1, 6]
[1, 7]
[1, 8]
[1, 9]
[2, 3]
[2, 4]
[2, 5]
[2, 6]
[2, 7]
[2, 8]
[2, 9]
[3, 4]
[3, 5]
[3, 6]
[3, 7]
[3, 8]
[3, 9]
[4, 5]
[4, 6]
[4, 7]
[4, 8]
[4, 9]
[5, 6]
[5, 7]
[5, 8]
[5, 9]
[6, 7]
[6, 8]
[6, 9]
[7, 8]
[7, 9]
[8, 9]

pour 3 chiffres :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 2, 7]
[1, 2, 8]
[1, 2, 9]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[1, 3, 7]
[1, 3, 8]
[1, 3, 9]
[1, 4, 5]
...........
[6, 7, 9]
[6, 8, 9]
[7, 8, 9]

Maintenant ce que je veux c'est d'avoir une fonction récursive qui me fournit toutes les combinaisons possibles
suivant une liste de chiffre donnée ou le nombre de caractères (2 chiffres, 3 chiffres .....) pour les combinaisons pourra varier de 2 à 10 aussi.

Code:

1
2
3
4
5
 
public List<Integer> listeCombinaison(List<Integer> maListe, int p)
{
        //ou p designe le nombre de caractères pour la combinaison et maListe la liste contenant les valeurs à combiner.
}

Désolé pour la longueur et Merci de votre aide.

13/01/2017, 13h38
ddoumeche

J'ai une solution bête et méchante consistant à stocker ces tuples et triplés sous formes de hash de string, les indices étant classés du plus haut au plus bas:

[1,4] => [1,4] => "1,4"
[4,1] => [1,4] => "1,4" (collision, on l'oublie)
[2,6,3] => [2,3,6] => "2,3,6"

Pour le tris de tes entiers, un simple Collections.sort(maListe) suffira mais essaye de la faire une seule fois.

Quid des combinaisons avec nombre dupliquée, genre [1,1,1] ?

Bonjour, est-ce que ceci conviendrait ?

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
 
public class TestMe {
 
	public static void generate(char[][] tabs, int[] indexes, int level) {
		if (level == tabs.length) {
			for (int i = 0; i < tabs.length; i++)
				System.out.print(tabs[i][indexes[i]]);
			System.out.println("");
			return;
		}
		for (int i = 0; i < tabs[level].length; i++) {
			indexes[level] = i;
			generate(tabs, indexes, level+1);
		}
	}
 
	public static void main(String[] args) {
		char[] tab1 = {'a', 'b', 'c'};
		char[] tab2 = {'d', 'e'};
		char[] tab3 = {'f', 'g', 'h', 'i'};
		char[][] tabs = {tab1, tab2, tab3};
		int[] indexes = {0, 0, 0};
		generate(tabs, indexes, 0);
	}
}