[java] Permutations et Combinaisons
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:
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)