Petit bout de code récursif pour calculer les combinaisons C(n,p) sans remise
Par exemple, pour p=3 et n=5 (0,1,2,3,4) on obtient:
[0,1,2] [0,1,3] [0,1,4] [0,2,3] [0,2,4] [0,3,4] [1,2,3] [1,2,4] [1,3,4] [2,3,4]
Code java : 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 static int n = 5; 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; } // ajoute un nouvel element candidat dans la liste // - sans ordre -> candidat: tous les elements // - avec ordre -> candidat: seulement les elements supérieurs au précédant int start=0; 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); }
NB: en mettant la variable "ordered=false", on obtient la liste de tous les arrangements avec remise (= n^p possibilités)
Partager