Genera combinazioni in Java

1. Introduzione

In questo tutorial, discuteremo la soluzione del problema delle k-combinazioni in Java .

Innanzitutto, discuteremo e implementeremo algoritmi sia ricorsivi che iterativi per generare tutte le combinazioni di una data dimensione. Quindi esamineremo le soluzioni utilizzando le librerie Java comuni.

2. Panoramica delle combinazioni

In poche parole, una combinazione è un sottoinsieme di elementi di un dato insieme .

A differenza delle permutazioni, l'ordine in cui scegliamo i singoli elementi non ha importanza. Invece, ci interessa solo se un particolare elemento è nella selezione.

Ad esempio, in un gioco di carte, dobbiamo distribuire 5 carte dal mazzo composto da 52 carte. Non abbiamo alcun interesse nell'ordine in cui sono state selezionate le 5 carte. Piuttosto, ci interessa solo quali carte sono presenti nella mano.

Alcuni problemi ci impongono di valutare tutte le possibili combinazioni. Per fare ciò, enumeriamo le varie combinazioni.

Il numero di modi distinti per scegliere elementi "r" dall'insieme di elementi "n" può essere espresso matematicamente con la seguente formula:

Pertanto, il numero di modi per scegliere gli elementi può crescere in modo esponenziale nel peggiore dei casi. Quindi, per grandi popolazioni, potrebbe non essere possibile enumerare le diverse selezioni.

In questi casi, possiamo selezionare casualmente alcune selezioni rappresentative. Il processo è chiamato campionamento .

Successivamente, esamineremo i vari algoritmi per elencare le combinazioni.

3. Algoritmi ricorsivi per generare combinazioni

Gli algoritmi ricorsivi di solito funzionano suddividendo un problema in problemi più piccoli simili. Questo processo continua fino a raggiungere la condizione di terminazione, che è anche il caso di base. Quindi risolviamo direttamente il caso di base.

Discuteremo due modi per suddividere il compito di scegliere gli elementi da un set. Il primo approccio divide il problema in termini di elementi dell'insieme. Il secondo approccio divide il problema tracciando solo gli elementi selezionati.

3.1. Partizionamento per elementi nell'intero set

Dividiamo il compito di selezionare gli elementi " r" da " n" elementi esaminando gli elementi uno per uno. Per ogni elemento del set, possiamo includerlo nella selezione o escluderlo.

Se includiamo la prima voce, allora dobbiamo scegliere “r - 1" elementi rimanenti “ n - 1" articoli . D'altra parte, se scartiamo il primo elemento, dobbiamo selezionare gli elementi " r" dai restanti elementi " n - 1" .

Questo può essere espresso matematicamente come:

Ora, esaminiamo l'implementazione ricorsiva di questo approccio:

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

Il metodo helper effettua due chiamate ricorsive a se stesso. La prima chiamata include l'elemento corrente. La seconda chiamata scarta l'elemento corrente.

Quindi, scriviamo il generatore di combinazioni usando questo metodo di supporto :

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

Nel codice precedente, il metodo generate imposta la prima chiamata al metodo helper e passa i parametri appropriati.

Quindi, chiamiamo questo metodo per generare combinazioni:

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

All'esecuzione del programma, otteniamo il seguente output:

[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

Infine, scriviamo il test case:

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

È facile osservare che la dimensione dello stack richiesta è il numero di elementi nel set. Quando il numero di elementi nel set è grande, diciamo, maggiore della profondità massima dello stack di chiamate, sovraccaricheremo lo stack e otterremo un'eccezione StackOverflowError .

Pertanto, questo approccio non funziona se il set di input è grande.

3.2. Partizionamento per elementi nella combinazione

Invece di tracciare gli elementi nel set di input, divideremo l'attività tenendo traccia degli elementi nella selezione .

Per prima cosa, ordiniamo gli elementi nel set di input utilizzando gli indici da "1" a " n" . Ora possiamo scegliere il primo elemento dai primi elementi " n-r + 1" .

Supponiamo di aver scelto l' elemento k - esimo . Quindi, dobbiamo scegliere gli elementi " r - 1" dai restanti elementi " n - k" indicizzati da " k + 1" a " n" .

Esprimiamo questo processo matematicamente come:

Successivamente, scriviamo il metodo ricorsivo per implementare questo approccio:

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

Nel codice sopra, il ciclo for sceglie l'elemento successivo, quindi chiama il metodo helper () in modo ricorsivo per scegliere gli elementi rimanenti . Ci fermiamo quando è stato selezionato il numero richiesto di elementi.

Successivamente, usiamo il metodo helper per generare le selezioni:

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

Infine, scriviamo un test case:

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

La dimensione dello stack di chiamate utilizzata da questo approccio è la stessa del numero di elementi nella selezione. Pertanto, questo approccio può funzionare per input di grandi dimensioni purché il numero di elementi da selezionare sia inferiore alla profondità massima dello stack di chiamate.

Se anche il numero di elementi da scegliere è elevato, questo metodo non funzionerà.

4. Algoritmo iterativo

Nell'approccio iterativo, iniziamo con una combinazione iniziale. Quindi, continuiamo a generare la combinazione successiva da quella corrente fino a quando non abbiamo generato tutte le combinazioni .

Generiamo le combinazioni in ordine lessicografico. Iniziamo con la combinazione lessicografica più bassa.

Per ottenere la combinazione successiva da quella corrente, troviamo la posizione più a destra nella combinazione corrente che può essere incrementata. Quindi, incrementiamo la posizione e generiamo la combinazione lessicografica più bassa possibile a destra di quella posizione.

Scriviamo il codice che segue questo approccio:

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

Quindi, scriviamo il test case:

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

Ora, usiamo alcune librerie Java per risolvere il problema.

5. Librerie Java che implementano combinazioni

Per quanto possibile, dovremmo riutilizzare le implementazioni di libreria esistenti invece di distribuire le nostre. In questa sezione, esploreremo le seguenti librerie Java che implementano combinazioni:

  • Apache Commons
  • Guaiava
  • CombinatoricsLib

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.

Abbiamo anche esaminato alcune implementazioni di librerie. In genere, li useremmo invece di rotolare i nostri.

Come al solito, il codice sorgente completo può essere trovato su GitHub.