Skip to content

Instantly share code, notes, and snippets.

@m-manu
Last active September 19, 2017 10:59
Show Gist options
  • Save m-manu/8adf4431a0d797c6724776d945428c0a to your computer and use it in GitHub Desktop.
Save m-manu/8adf4431a0d797c6724776d945428c0a to your computer and use it in GitHub Desktop.
Helps you generate possible combinations of array of arrays in a thread-safe way. Use this only if you have duplicates. If your input collection contains unique collections, use Guava's `Sets.cartesianProduct` method.
package manu.sandbox.utils;
import java.util.Deque;
import java.util.LinkedList;
/**
* Helps you generate possible combinations of array of arrays in a thread-safe way
*/
public class CombinationGenerator<T> {
private final Deque<T> buffer = new LinkedList<>();
private final T[][] input, output;
private int index = 0;
private CombinationGenerator(T[][] input, T[][] output) {
this.input = input;
this.output = output;
}
private void computeCombinations(int i, int n) {
if (i == n) {
int k = 0;
for (T s : buffer) {
output[index][k] = s;
k++;
}
index++;
return;
}
for (int j = 0; j < input[i].length; j++) {
buffer.add(input[i][j]);
computeCombinations(i + 1, n);
buffer.pollLast();
}
}
/**
* Generate all possible combinations of mutually exclusive strings.<br>
* e.g. An input of<br>
* <code>{{"Delhi", "Mumbai"}, {"Airport", "Bus stand"}}</code><br>
* gives you below output:<br>
* <code>{{"Delhi", "Airport"}, {"Mumbai", "Airport"}, {"Delhi", "Bus stand"}, {"Mumbai", "Bus stand"}}</code>
* <br>
*
* @param arrayOfArrays Input array of arrays
* @return An array of all combinations (arrays) possible
* @throws IllegalArgumentException If you pass invalid arguments (e.g. empty or null arrays)
*/
public static String[][] generate(String[][] arrayOfArrays) {
int outputLength = getOutputLength(arrayOfArrays);
CombinationGenerator<String> generator = new CombinationGenerator<>(arrayOfArrays, new String[outputLength][arrayOfArrays.length]);
generator.computeCombinations(0, arrayOfArrays.length);
return generator.output;
}
private static <T> int getOutputLength(T[][] arrayOfArrays) {
if (arrayOfArrays == null || arrayOfArrays.length == 0) {
throw new IllegalArgumentException("Input array is null or empty");
}
int outputLength = 1;
for (T[] array : arrayOfArrays) {
outputLength *= array == null ? 0 : array.length;
}
if (outputLength == 0) {
throw new IllegalArgumentException("One or more of the sub-arrays passed is null or empty");
}
return outputLength;
}
}
package manu.sandbox.utils;
import com.google.common.collect.Sets;
import org.junit.Test;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class CombinationGeneratorTest {
@Test
public void testValidCases() {
List<String[][]> testCases = Arrays.asList(
new String[][]{{"India"}, {"idea"}, {"Male", "Female"}},
new String[][]{{"Delhi", "Mumbai"}, {"Airport", "Railway Station", "Bus stand"}, {"Cab", "Bus"}},
new String[][]{{"Friendly", "Arrogant"}, {"White", "Black", "Brown"}, {"Cat", "Dog"}, {"Owner"}}
);
for (String[][] testCase : testCases) {
int product = 1;
for (String[] combination : testCase) {
product *= combination.length;
}
String[][] combinations = CombinationGenerator.generate(testCase);
assertEquals("Number of combinations generated is not product of lengths of arrays", combinations.length, product);
Set<List<String>> combinationsAsString = new HashSet<>(product);
for (String[] combination : combinations) {
assertEquals(String.format("Combination %s is of unexpected length", Arrays.toString(combination)), combination.length, testCase.length);
for (int i = 0; i < combination.length; i++) {
assertTrue(String.format("Combination %s contains %s (at position %d), which isn't part of input %s", Arrays.toString(combination), combination[i], i, Arrays.toString(testCase[i])), Sets.newHashSet(testCase[i]).contains(combination[i]));
}
assertTrue(String.format("Combination %s got repeated", Arrays.toString(combination)), combinationsAsString.add(Arrays.asList(combination)));
}
}
}
@Test(expected = IllegalArgumentException.class)
public void testEmptySubArray() {
CombinationGenerator.generate(new String[][]{{"a", "b"}, {}});
}
@Test(expected = IllegalArgumentException.class)
public void testEmptyArray() {
CombinationGenerator.generate(null);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment