Générer des combinaisons en Java

1. Introduction

Dans ce tutoriel, nous discuterons de la solution du problème des k-combinaisons en Java .

Tout d'abord, nous discuterons et implémenterons des algorithmes récursifs et itératifs pour générer toutes les combinaisons d'une taille donnée. Ensuite, nous examinerons les solutions utilisant les bibliothèques Java courantes.

2. Aperçu des combinaisons

En termes simples, une combinaison est un sous-ensemble d'éléments d'un ensemble donné .

Contrairement aux permutations, l'ordre dans lequel nous choisissons les éléments individuels n'a pas d'importance. Au lieu de cela, nous nous soucions uniquement de savoir si un élément particulier est dans la sélection.

Par exemple, dans un jeu de cartes, nous devons distribuer 5 cartes du pack composé de 52 cartes. Nous n'avons aucun intérêt dans l'ordre dans lequel les 5 cartes ont été sélectionnées. Au contraire, nous ne nous soucions que des cartes présentes dans la main.

Certains problèmes nous obligent à évaluer toutes les combinaisons possibles. Pour ce faire, nous énumérons les différentes combinaisons.

Le nombre de façons distinctes de choisir des éléments «r» parmi l'ensemble des «n» éléments peut être exprimé mathématiquement avec la formule suivante:

Par conséquent, le nombre de façons de choisir les éléments peut augmenter de façon exponentielle dans le pire des cas. Par conséquent, pour les grandes populations, il peut ne pas être possible d'énumérer les différentes sélections.

Dans de tels cas, nous pouvons sélectionner au hasard quelques sélections représentatives. Le processus s'appelle l' échantillonnage .

Ensuite, nous passerons en revue les différents algorithmes pour lister les combinaisons.

3. Algorithmes récursifs pour générer des combinaisons

Les algorithmes récursifs fonctionnent généralement en partitionnant un problème en problèmes similaires plus petits. Ce processus se poursuit jusqu'à ce que nous atteignions la condition de fin, qui est également le cas de base. Ensuite, nous résolvons directement le cas de base.

Nous discuterons de deux façons de subdiviser la tâche de choix des éléments d'un ensemble. La première approche divise le problème en termes d'éléments de l'ensemble. La seconde approche divise le problème en suivant uniquement les éléments sélectionnés.

3.1. Partitionnement par éléments dans l'ensemble complet

Divisons la tâche de sélection des éléments « parmi « éléments en inspectant les éléments un par un. Pour chaque élément de l'ensemble, nous pouvons soit l'inclure dans la sélection, soit l'exclure.

Si l' on inclut le premier élément, nous devons choisir « r - 1" éléments des autres « n - 1" articles . D'un autre côté, si nous rejetons le premier élément, nous devons sélectionner les éléments « parmi les éléments « n - 1» restants .

Cela peut être exprimé mathématiquement par:

Maintenant, regardons la mise en œuvre récursive de cette approche:

private void helper(List combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else if (start <= end) { data[index] = start; helper(combinations, data, start + 1, end, index + 1); helper(combinations, data, start + 1, end, index); } }

La méthode d' assistance effectue deux appels récursifs à elle-même. Le premier appel inclut l'élément actuel. Le deuxième appel rejette l'élément actuel.

Ensuite, écrivons le générateur de combinaison en utilisant cette méthode d' assistance :

public List generate(int n, int r) { List combinations = new ArrayList(); helper(combinations, new int[r], 0, n-1, 0); return combinations; }

Dans le code ci-dessus, la méthode generate configure le premier appel à la méthode d' assistance et transmet les paramètres appropriés.

Ensuite, appelons cette méthode pour générer des combinaisons:

List combinations = generate(N, R); for (int[] combination : combinations) { System.out.println(Arrays.toString(combination)); } System.out.printf("generated %d combinations of %d items from %d ", combinations.size(), R, N);

Lors de l'exécution du programme, nous obtenons la sortie suivante:

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] generated 10 combinations of 2 items from 5

Enfin, écrivons le cas de test:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount() { SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Il est facile d'observer que la taille de pile requise est le nombre d'éléments de l'ensemble. Lorsque le nombre d'éléments dans l'ensemble est grand, par exemple supérieur à la profondeur maximale de la pile d'appels, nous allons déborder de la pile et obtenir un StackOverflowError .

Par conséquent, cette approche ne fonctionne pas si le jeu d'entrées est volumineux.

3.2. Partitionnement par éléments dans la combinaison

Au lieu de suivre les éléments de l'ensemble d'entrée, nous diviserons la tâche en suivant les éléments de la sélection .

Commençons par ordonner les éléments de l'ensemble d'entrée en utilisant les indices «1» à « . Maintenant, nous pouvons choisir le premier élément parmi les premiers éléments « n-r + 1» .

Supposons que nous ayons choisi le kième élément. Ensuite, nous devons choisir « r - 1» éléments parmi les « n - k» éléments restants indexés « k + 1» à « .

Nous exprimons ce processus mathématiquement comme:

Ensuite, écrivons la méthode récursive pour implémenter cette approche:

private void helper(List combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else { int max = Math.min(end, end + 1 - data.length + index); for (int i = start; i <= max; i++) { data[index] = i; helper(combinations, data, i + 1, end, index + 1); } } }

Dans le code ci-dessus, la boucle for choisit l'élément suivant, puis elle appelle la méthode helper () de manière récursive pour choisir les éléments restants . Nous nous arrêtons lorsque le nombre d'articles requis a été sélectionné.

Ensuite, utilisons la méthode d' assistance pour générer des sélections:

public List generate(int n, int r) { List combinations = new ArrayList(); helper(combinations, new int[r], 0, n - 1, 0); return combinations; }

Enfin, écrivons un cas de test:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount() { SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

La taille de la pile d'appels utilisée par cette approche est la même que le nombre d'éléments dans la sélection. Par conséquent, cette approche peut fonctionner pour de grandes entrées tant que le nombre d'éléments à sélectionner est inférieur à la profondeur maximale de la pile d'appels.

Si le nombre d'éléments à choisir est également important, cette méthode ne fonctionnera pas.

4. Algorithme itératif

Dans l'approche itérative, nous partons d'une combinaison initiale. Ensuite, nous continuons à générer la combinaison suivante à partir de la combinaison actuelle jusqu'à ce que nous ayons généré toutes les combinaisons .

Générons les combinaisons dans l'ordre lexicographique. Nous commençons par la combinaison lexicographique la plus basse.

Afin d'obtenir la combinaison suivante à partir de la combinaison actuelle, nous trouvons l'emplacement le plus à droite dans la combinaison actuelle qui peut être incrémentée. Ensuite, nous incrémentons l'emplacement et générons la combinaison lexicographique la plus basse possible à droite de cet emplacement.

Écrivons le code qui suit cette approche:

public List generate(int n, int r) { List combinations = new ArrayList(); int[] combination = new int[r]; // initialize with lowest lexicographic combination for (int i = 0; i < r; i++) { combination[i] = i; } while (combination[r - 1] < n) { combinations.add(combination.clone()); // generate next combination in lexicographic order int t = r - 1; while (t != 0 && combination[t] == n - r + t) { t--; } combination[t]++; for (int i = t + 1; i < r; i++) { combination[i] = combination[i - 1] + 1; } } return combinations; }

Ensuite, écrivons le cas de test:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount() { IterativeCombinationGenerator generator = new IterativeCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Maintenant, utilisons quelques bibliothèques Java pour résoudre le problème.

5. Bibliothèques Java mettant en œuvre des combinaisons

Dans la mesure du possible, nous devrions réutiliser les implémentations de bibliothèques existantes au lieu de déployer les nôtres. Dans cette section, nous explorerons les bibliothèques Java suivantes qui implémentent des combinaisons:

  • Apache Commons
  • Goyave
  • CombinatoireLib

5.1. Apache Commons

The CombinatoricsUtils class from Apache Commons provides many combination utility functions. In particular, the combinationsIterator method returns an iterator that will generate combinations in lexicographic order.

First, let's add the Maven dependency commons-math3 to the project:

 org.apache.commons commons-math3 3.6.1 

Next, let's use the combinationsIterator method to print the combinations:

public static void generate(int n, int r) { Iterator iterator = CombinatoricsUtils.combinationsIterator(n, r); while (iterator.hasNext()) { final int[] combination = iterator.next(); System.out.println(Arrays.toString(combination)); } }

5.2. Google Guava

The Sets class from Guava library provides utility methods for set-related operations. The combinations method returns all subsets of a given size.

First, let's add the maven dependency for the Guava library to the project:

 com.google.guava guava 27.0.1-jre 

Next, let's use the combinations method to generate combinations:

Set
    
      combinations = Sets.combinations(ImmutableSet.of(0, 1, 2, 3, 4, 5), 3);
    

Here, we are using the ImmutableSet.of method to create a set from the given numbers.

5.3. CombinatoricsLib

CombinatoricsLib is a small and simple Java library for permutations, combinations, subsets, integer partitions, and cartesian product.

To use it in the project, let's add the combinatoricslib3 Maven dependency:

 com.github.dpaukov combinatoricslib3 3.3.0 

Next, let's use the library to print the combinations:

Generator.combination(0, 1, 2, 3, 4, 5) .simple(3) .stream() .forEach(System.out::println);

This produces the following output on execution:

[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 3, 4] [0, 3, 5] [0, 4, 5] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5]

More examples are available at combinatoricslib3-example.

6. Conclusion

In this article, we implemented a few algorithms to generate combinations.

Nous avons également examiné quelques implémentations de bibliothèques. En règle générale, nous les utiliserions au lieu de rouler les nôtres.

Comme d'habitude, le code source complet peut être trouvé sur GitHub.