Panoramica dei problemi combinatori in Java

1. Panoramica

In questo tutorial impareremo come risolvere alcuni comuni problemi combinatori. Molto probabilmente non sono molto utili nel lavoro quotidiano; tuttavia, sono interessanti dal punto di vista algoritmico. Potremmo trovarli utili a scopo di test.

Tieni presente che esistono molti approcci diversi per risolvere questi problemi. Abbiamo cercato di rendere le soluzioni presentate di facile comprensione.

2. Generazione di permutazioni

Per prima cosa, iniziamo con le permutazioni. Una permutazione è un atto di riorganizzare una sequenza in modo tale che abbia un ordine diverso.

Come sappiamo dalla matematica, per una sequenza di n elementi, ci sono n! diverse permutazioni . n! è nota come operazione fattoriale:

n! = 1 * 2 *… * n

Quindi, ad esempio, per una sequenza [1, 2, 3] ci sono sei permutazioni:

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

Il fattoriale cresce molto velocemente: per una sequenza di 10 elementi, abbiamo 3.628.800 diverse permutazioni! In questo caso parliamo di sequenze permutanti, dove ogni singolo elemento è diverso .

2.1. Algoritmo

È una buona idea pensare di generare permutazioni in modo ricorsivo. Introduciamo l'idea di stato. Consisterà di due cose: la permutazione corrente e l'indice dell'elemento attualmente elaborato.

L'unico lavoro da fare in un tale stato è scambiare l'elemento con ogni rimanente ed eseguire una transizione a uno stato con la sequenza modificata e l'indice aumentato di uno.

Illustriamo con un esempio.

Vogliamo generare tutte le permutazioni per una sequenza di quattro elementi - [1, 2, 3, 4] . Quindi, ci saranno 24 permutazioni. L'illustrazione seguente presenta i passaggi parziali dell'algoritmo:

Ogni nodo dell'albero può essere inteso come uno stato. Le cifre rosse in alto indicano l'indice dell'elemento attualmente elaborato. Le cifre verdi nei nodi illustrano gli scambi.

Quindi, iniziamo nello stato [1, 2, 3, 4] con un indice uguale a zero. Scambiamo il primo elemento con ogni elemento, compreso il primo, che non scambia nulla, e passiamo allo stato successivo.

Ora, le nostre permutazioni desiderate si trovano nell'ultima colonna a destra.

2.2. Implementazione Java

L'algoritmo scritto in Java è breve:

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); } }
    

La nostra funzione accetta tre parametri: la sequenza attualmente elaborata, i risultati (permutazioni) e l'indice dell'elemento attualmente in elaborazione.

La prima cosa da fare è controllare se abbiamo raggiunto l'ultimo elemento. In tal caso, aggiungiamo la sequenza all'elenco dei risultati.

Quindi, nel ciclo for, eseguiamo uno scambio, eseguiamo una chiamata ricorsiva al metodo e quindi scambiamo nuovamente l'elemento.

L'ultima parte è un piccolo trucco per le prestazioni: possiamo operare sullo stesso oggetto sequenza tutto il tempo senza dover creare una nuova sequenza per ogni chiamata ricorsiva.

Potrebbe anche essere una buona idea nascondere la prima chiamata ricorsiva sotto un metodo di facciata:

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

Tieni presente che l'algoritmo mostrato funzionerà solo per sequenze di elementi unici! Applicare lo stesso algoritmo per sequenze con elementi ricorrenti ci darà ripetizioni.

3. Generazione del Powerset di un Set

Un altro problema comune è la generazione del set di potenza di un set. Partiamo dalla definizione:

powerset (o power set) dell'insieme S è l'insieme di tutti i sottoinsiemi di S compreso l'insieme vuoto e S stesso

Quindi, ad esempio, dato un insieme [a, b, c] , il powerset contiene otto sottoinsiemi:

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

Sappiamo dalla matematica che, per un insieme contenente n elementi, il powerset dovrebbe contenere 2 ^ n sottoinsiemi . Anche questo numero cresce rapidamente, ma non quanto fattoriale.

3.1. Algoritmo

Questa volta penseremo anche in modo ricorsivo. Ora, il nostro stato sarà composto da due cose: l'indice dell'elemento attualmente in fase di elaborazione in un insieme e un accumulatore.

Dobbiamo prendere una decisione con due scelte in ogni stato: se mettere o meno l'elemento corrente nell'accumulatore. Quando il nostro indice raggiunge la fine dell'insieme, abbiamo un possibile sottoinsieme. In tal modo, possiamo generare ogni possibile sottoinsieme.

3.2. Implementazione Java

Il nostro algoritmo scritto in Java è abbastanza leggibile:

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); } }
    

La nostra funzione accetta quattro parametri: un insieme per il quale vogliamo generare sottoinsiemi, il gruppo di potenza risultante, l'accumulatore e l'indice dell'elemento attualmente elaborato.

Per semplicità, manteniamo i nostri set in elenchi. Vogliamo avere un rapido accesso agli elementi specificati da index, cosa che possiamo ottenere con List , ma non con Set .

Inoltre, un singolo elemento è rappresentato da una singola lettera ( classe di caratteri in Java).

Innanzitutto, controlliamo se l'indice supera la dimensione impostata. In tal caso, inseriamo l'accumulatore nel set di risultati, altrimenti:

  • mettere l'elemento attualmente considerato nell'accumulatore
  • effettua una chiamata ricorsiva con indice incrementato e accumulatore esteso
  • rimuovere l'ultimo elemento dall'accumulatore, che abbiamo aggiunto in precedenza
  • ripetere una chiamata con accumulatore invariato e indice incrementato

Ancora una volta, nascondiamo l'implementazione con un metodo di facciata:

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

4. Generazione di combinazioni

Ora è il momento di affrontare le combinazioni. Lo definiamo come segue:

k -combinazione di un insieme S è un sottoinsieme di k elementi distinti da S, dove l'ordine degli elementi non ha importanza

Il numero di k -combinazioni è descritto dal coefficiente binomiale:

Quindi, ad esempio, per l'insieme [a, b, c] abbiamo tre 2 combinazioni:

[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.

Come al solito, il codice sorgente completo, con i test, è disponibile su GitHub.