Présentation des problèmes de combinaison en Java

1. Vue d'ensemble

Dans ce didacticiel, nous allons apprendre à résoudre quelques problèmes combinatoires courants. Ils ne sont probablement pas très utiles dans un travail quotidien; cependant, ils sont intéressants du point de vue algorithmique. Nous pouvons les trouver utiles à des fins de test.

Gardez à l'esprit qu'il existe de nombreuses approches différentes pour résoudre ces problèmes. Nous avons essayé de rendre les solutions présentées faciles à saisir.

2. Génération de permutations

Commençons par les permutations. Une permutation est un acte de réarrangement d'une séquence de telle manière qu'elle ait un ordre différent.

Comme nous le savons par les mathématiques, pour une suite de n éléments, il y a n! différentes permutations . n! est connue sous le nom d'opération factorielle:

n! = 1 * 2 *… * n

Ainsi, par exemple, pour une séquence [1, 2, 3], il y a six permutations:

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Factorielle croît très vite - pour une séquence de 10 éléments, nous avons 3 628 800 permutations différentes! Dans ce cas, nous parlons de permutation de séquences, où chaque élément est différent .

2.1. Algorithme

C'est une bonne idée de penser à générer des permutations de manière récursive. Introduisons l'idée de l'État. Il se composera de deux choses: la permutation actuelle et l'indice de l'élément actuellement traité.

Le seul travail à faire dans un tel état est d'échanger l'élément avec chaque élément restant et d'effectuer une transition vers un état avec la séquence modifiée et l'index augmenté de un.

Illustrons avec un exemple.

Nous voulons générer toutes les permutations pour une séquence de quatre éléments - [1, 2, 3, 4] . Donc, il y aura 24 permutations. L'illustration ci-dessous présente les étapes partielles de l'algorithme:

Chaque nœud de l'arbre peut être compris comme un état. Les chiffres rouges en haut indiquent l'index de l'élément actuellement traité. Les chiffres verts dans les nœuds illustrent les swaps.

On commence donc dans l'état [1, 2, 3, 4] avec un index égal à zéro. Nous échangeons le premier élément avec chaque élément - y compris le premier, qui n'échange rien - et passons à l'état suivant.

Maintenant, nos permutations souhaitées sont situées dans la dernière colonne à droite.

2.2. Implémentation Java

L'algorithme écrit en Java est court:

private static void permutationsInternal(List sequence, List
    
      results, int index) { if (index == sequence.size() - 1) { permutations.add(new ArrayList(sequence)); } for (int i = index; i < sequence.size(); i++) { swap(sequence, i, index); permutationsInternal(sequence, permutations, index + 1); swap(sequence, i, index); } }
    

Notre fonction prend trois paramètres: la séquence actuellement traitée, les résultats (permutations) et l'index de l'élément en cours de traitement.

La première chose à faire est de vérifier si nous avons atteint le dernier élément. Si tel est le cas, nous ajoutons la séquence à la liste des résultats.

Ensuite, dans la boucle for, nous effectuons un échange, faisons un appel récursif à la méthode, puis échangeons l'élément en arrière.

La dernière partie est une petite astuce de performance - nous pouvons opérer sur le même objet séquence tout le temps sans avoir à créer une nouvelle séquence pour chaque appel récursif.

Il peut également être judicieux de masquer le premier appel récursif sous une méthode de façade:

public static List
    
      generatePermutations(List sequence) { List
     
       permutations = new ArrayList(); permutationsInternal(sequence, permutations, 0); return permutations; } 
     
    

Gardez à l'esprit que l'algorithme présenté ne fonctionnera que pour des séquences d'éléments uniques! Appliquer le même algorithme pour les séquences avec des éléments récurrents nous donnera des répétitions.

3. Génération de l'ensemble de puissance d'un ensemble

Un autre problème courant est la génération de l'ensemble de puissance d'un ensemble. Commençons par la définition:

l'ensemble de puissance (ou ensemble de puissance) de l'ensemble S est l'ensemble de tous les sous-ensembles de S, y compris l'ensemble vide et S lui-même

Ainsi, par exemple, étant donné un ensemble [a, b, c] , l'ensemble de pouvoirs contient huit sous-ensembles:

[] [a] [b] [c] [a, b] [a, c] [b, c] [a, b, c]

Nous savons d'après les mathématiques que, pour un ensemble contenant n éléments, l'ensemble de puissance doit contenir 2 ^ n sous-ensembles . Ce nombre augmente également rapidement, mais pas aussi vite que factoriel.

3.1. Algorithme

Cette fois, nous penserons également de manière récursive. Maintenant, notre état sera constitué de deux choses: l'index de l'élément en cours de traitement dans un ensemble et un accumulateur.

Nous devons prendre une décision avec deux choix dans chaque état: mettre ou non l'élément courant dans l'accumulateur. Lorsque notre index atteint la fin de l'ensemble, nous avons un sous-ensemble possible. De cette manière, nous pouvons générer tous les sous-ensembles possibles.

3.2. Implémentation Java

Our algorithm written in Java is pretty readable:

private static void powersetInternal( List set, List
    
      powerset, List accumulator, int index) { if (index == set.size()) { results.add(new ArrayList(accumulator)); } else { accumulator.add(set.get(index)); powerSetInternal(set, powerset, accumulator, index + 1); accumulator.remove(accumulator.size() - 1); powerSetInternal(set, powerset, accumulator, index + 1); } }
    

Our function takes four parameters: a set for which we want to generate subsets, the resulting powerset, the accumulator, and the index of the currently processed element.

For simplicity, we keep our sets in lists. We want to have fast access to elements specified by index, which we can achieve it with List, but not with Set.

Additionally, a single element is represented by a single letter (Character class in Java).

First, we check if the index exceeds the set size. If it does, then we put the accumulator into the result set, otherwise we:

  • put the currently considered element into the accumulator
  • make a recursive call with incremented index and extended accumulator
  • remove the last element from the accumulator, which we added previously
  • do a call again with unchanged accumulator and the incremented index

Again, we hide the implementation with a facade method:

public static List
    
      generatePowerset(List sequence) { List
     
       powerset = new ArrayList(); powerSetInternal(sequence, powerset, new ArrayList(), 0); return powerset; }
     
    

4. Generating Combinations

Now, it's time to tackle combinations. We define it as follows:

k-combination of a set S is a subset of k distinct elements from S, where an order of items doesn't matter

The number of k-combinations is described by the binomial coefficient:

So, for example, for the set [a, b, c] we have three 2-combinations:

[a, b] [a, c] [b, c]

Combinations have many combinatorial usages and explanations. As an example, let's say we have a football league consisting of 16 teams. How many different matches can we see?

The answer is , which evaluates to 120.

4.1. Algorithm

Conceptually, we'll do something similar to the previous algorithm for powersets. We'll have a recursive function, with state consisting of the index of the currently processed element and an accumulator.

Again, we've got the same decision for each state: Do we add the element to the accumulator?This time, though, we have an additional restriction – our accumulator can't have more than k elements.

It's worth noticing that the binomial coefficient doesn't necessarily need to be a huge number. For example:

is equal to 4,950, while

has 30 digits!

4.2. Java Implementation

For simplicity, we assume that elements in our set are integers.

Let's take a look at the Java implementation of the algorithm:

private static void combinationsInternal( List inputSet, int k, List
    
      results, ArrayList accumulator, int index) { int needToAccumulate = k - accumulator.size(); int canAcculumate = inputSet.size() - index; if (accumulator.size() == k) { results.add(new ArrayList(accumulator)); } else if (needToAccumulate <= canAcculumate) { combinationsInternal(inputSet, k, results, accumulator, index + 1); accumulator.add(inputSet.get(index)); combinationsInternal(inputSet, k, results, accumulator, index + 1); accumulator.remove(accumulator.size() - 1); } }
    

This time, our function has five parameters: an input set, k parameter, a result list, an accumulator, and the index of the currently processed element.

We start by defining helper variables:

  • needToAccumulate – indicates how many more elements we need to add to our accumulator to get a proper combination
  • canAcculumate – indicates how many more elements we can add to our accumulator

Now, we check if our accumulator size is equal to k. If so, then we can put the copied array into the results list.

In another case, if we still have enough elements in the remaining part of the set, we make two separate recursive calls: with and without the currently processed element being put into the accumulator. This part is analogous to how we generated the powerset earlier.

Of course, this method could've been written to work a little bit faster. For example, we could declare needToAccumulate and canAcculumate variables later. However, we are focused on readability.

Again, a facade method hides the implementation:

public static List
    
      combinations(List inputSet, int k) { List
     
       results = new ArrayList(); combinationsInternal(inputSet, k, results, new ArrayList(), 0); return results; }
     
    

5. Summary

In this article, we've discussed different combinatorial problems. Additionally, we've shown simple algorithms to solve them with implementations in Java. In some cases, these algorithms can help with unusual testing needs.

Comme d'habitude, le code source complet, avec des tests, est disponible sur GitHub.