I am looking for a Java library that can produce combinations of vectors like this:
Given:
vector1 = {A, B, C}
vector2 = {0, 1, 2}
Produce the following combinations:
A, 0
A, 1
A, 2
B, 0
B, 1
B, 2
C, 0
C, 1
C, 2
The number of vectors give the number of dimensions (columns of the combinations).
In Python the function product from the intertools library does exactly this, but I haven't seen any Java library to do it.
Thanks.
You can use java8 streams to do it almost as simply as if you called a function from a library. Assuming you already have:
List<String> vector1 = Arrays.asList("A","B","C");
List<Integer> vector2 = Arrays.asList(1,2,3);
You can get your expected result in a following way
Map<String, Integer> result = new HashMap<>();
vector1.stream().forEach(o1 -> vector2.stream().forEach(o2 -> result.put(o1,o2)));
Or if you prefer List of Tuples, then you need to either create a class for your pairs, or use a Tuple
Solution #1 : You can use a map to associate a string with a list of integers.
public static void main(String[] args) {
List<String> v1 = Arrays.asList("A", "B", "C");
List<Integer> v2 = Arrays.asList(0, 1, 2);
Map<String, List<Integer>> product = getProduct(v1, v2);
}
public static Map<String, List<Integer>> getProduct(List<String> v1, List<Integer> v2) {
Map<String, List<Integer>> product = new HashMap<>();
for (String e1 : v1) {
product.put(e1, v2);
}
return product;
}
The data are represented this way :
Solution #2 : You create a list of Combination objects.
public class Combination<T1, T2> {
protected final T1 value1;
protected final T2 value2;
public Combination(T1 value1, T2 value2) {
this.value1 = value1;
this.value2 = value2;
}
public T1 getValue1() {
return value1;
}
public T2 getValue2() {
return value2;
}
}
public class CombinationGenerator<T1, T2> {
protected final List<T1> values1;
protected final List<T2> values2;
public CombinationGenerator(List<T1> values1, List<T2> values2) {
this.values1 = values1;
this.values2 = values2;
}
public List<Combination<T1, T2>> getCombinations() {
List<Combination<T1, T2>> combinations = new LinkedList<>();
for (T1 e1 : values1) {
for (T2 e2 : values2) {
combinations.add(new Combination<>(e1, e2));
}
}
return combinations;
}
}
public static void main(String[] args) {
List<String> v1 = Arrays.asList("A", "B", "C");
List<Integer> v2 = Arrays.asList(0, 1, 2);
CombinationGenerator<String, Integer> combGen = new CombinationGenerator<>(v1, v2);
List<Combination<String, Integer>> combinations = combGen.getCombinations();
}
This solution returns a list of 9 combinations :
Edit: For the solution #1, you can use Guava's Multimap
public static Multimap<String, Integer> getCombinations(List<String> v1, List<Integer> v2) {
Multimap<String, Integer> combinations = ArrayListMultimap.create();
for (String e1 : v1) {
for (Integer e2 : v2) {
combinations.put(e1, e2);
}
}
return combinations;
}
Previous given answers were good but not generalizable for N dimensions.
This code is generalizable, and correct.
/*
* www.javagl.de - Utilities - Combinatorics
*
* Copyright (c) 2008-2013 Marco Hutter - http://www.javagl.de
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
package de.javagl.utils.math.combinatorics;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
/**
* A class providing an iterator over all combinations of a certain number
* of elements, where the valid ranges may be different for each element
* of the combination. For a set S = { S0, S1, ... Sn } there will be
* |S0| * |S1| * ... * |Sn| possible combinations. Example:<br />
* <pre>
* S0 = {A,B,C}, |S0| = 3
* S1 = {D,E} , |S1| = 2
* S2 = {A,E} , |S2| = 2
* S = { S0, S1, S2 }
* m = |S0| * |S1| * |S0| = 3 * 2 * 2 = 12 combinations
*
* Combinations:
* [A, D, A]
* [A, D, E]
* [A, E, A]
* [A, E, E]
* [B, D, A]
* [B, D, E]
* [B, E, A]
* [B, E, E]
* [C, D, A]
* [C, D, E]
* [C, E, A]
* [C, E, E]
* </pre>
*
* @param <T> The type of the elements
*/
public final class MixedRangeCombinationIterable<T> implements Iterable<List<T>>
{
/**
* The input elements
*/
private List<? extends Collection<? extends T>> sets;
/**
* The total number of elements that the iterator will provide
*/
private final int numElements;
/**
* Creates an iterable over all combinations of one element
* of each of the given sets.
*
* @param sets The input sets
*/
public MixedRangeCombinationIterable(
List<? extends Collection<? extends T>> sets)
{
this.sets = sets;
int m = 0;
if (sets.size() > 0)
{
m = 1;
}
for (Collection<? extends T> set : sets)
{
m *= set.size();
}
this.numElements = m;
}
@Override
public Iterator<List<T>> iterator()
{
return new Iterator<List<T>>()
{
/**
* The element counter
*/
private int current = 0;
/**
* The current combination
*/
private List<T> currentCombination = new ArrayList<T>();
/**
* The iterators over the individual sets
*/
private List<Iterator<? extends T>> subIterators =
new ArrayList<Iterator<? extends T>>(
Collections.<Iterator<? extends T>>nCopies(
sets.size(), null));
// Initialize the sub-iterators and the first combination
{
if (numElements > 0)
{
for (int i=0; i<sets.size(); i++)
{
Iterator<? extends T> subIterator =
sets.get(i).iterator();
subIterators.set(i, subIterator);
currentCombination.add(subIterator.next());
}
}
}
@Override
public boolean hasNext()
{
return current < numElements;
}
@Override
public List<T> next()
{
if (!hasNext())
{
throw new NoSuchElementException("No more elements");
}
List<T> result = new ArrayList<T>(currentCombination);
increase(sets.size()-1);
current++;
return result;
}
/**
* Increases the selection of elements by one.
*
* @param index The index to increase
*/
private void increase(int index)
{
if (index < 0)
{
return;
}
Iterator<? extends T> subIterator = subIterators.get(index);
if (subIterator.hasNext())
{
currentCombination.set(index, subIterator.next());
}
else
{
subIterator = sets.get(index).iterator();
subIterators.set(index, subIterator);
currentCombination.set(index, subIterator.next());
increase(index-1);
}
}
@Override
public void remove()
{
throw new UnsupportedOperationException(
"May not remove elements from a combination");
}
};
}
}
A typical usage would be:
List<List<Integer>> inputs = new ArrayList<List<Integer>>();
input.add(Arrays.asList(0, 1, 2));
input.add(Arrays.asList(0, 1, 2, 3));
input.add(Arrays.asList(0, 1));
MixedRangeCombinationIterable<Integer> product =
new MixedRangeCombinationIterable(inputs)
for(List<Integer> combination: product){
System.out.println(combination)
}
The following is a class that computes such a vector product, which is also referred to as the Cartesian Product of the input space. It is generalized for arbitrary data types, and an arbitrary number of dimensions.
(Originally, I published it on GitHub, but now it is released here under the usual stackoverflow license)
It receives a list of collections in the constructor. Each of these collections provides an iterator that is used to iterate over the respective dimension. The whole class is itself implemented as an Iterable (basically only wrapping the corresponding Iterator class). At each point in time, this iterator only maintains a list of the "current" iterators of the collections, and returns the corresponding elements and increases the iterators when next() is called.
The advantage of this approach is that it is not necessary the hold the whole cartesian product in memory. It is possible to iterate over a cartesian product that is larger than the available physical memory (which may be important, considering that cartesian products tend to become large).
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
/**
* A class providing an iterator over all combinations of a certain number
* of elements, where the valid ranges may be different for each element
* of the combination. For a set S = { S0, S1, ... Sn } there will be
* |S0| * |S1| * ... * |Sn| possible combinations. Example:<br />
* <pre>
* S0 = {A,B,C}, |S0| = 3
* S1 = {D,E} , |S1| = 2
* S2 = {A,E} , |S2| = 2
* S = { S0, S1, S2 }
* m = |S0| * |S1| * |S0| = 3 * 2 * 2 = 12 combinations
*
* Combinations:
* [A, D, A]
* [A, D, E]
* [A, E, A]
* [A, E, E]
* [B, D, A]
* [B, D, E]
* [B, E, A]
* [B, E, E]
* [C, D, A]
* [C, D, E]
* [C, E, A]
* [C, E, E]
* </pre>
*
* @param <T> The type of the elements
*/
public final class MixedRangeCombinationIterable<T> implements Iterable<List<T>>
{
/**
* The input elements
*/
private List<? extends Collection<? extends T>> sets;
/**
* The total number of elements that the iterator will provide
*/
private final int numElements;
/**
* Creates an iterable over all combinations of one element
* of each of the given sets.
*
* @param sets The input sets
*/
public MixedRangeCombinationIterable(
List<? extends Collection<? extends T>> sets)
{
this.sets = sets;
int m = 0;
if (sets.size() > 0)
{
m = 1;
}
for (Collection<? extends T> set : sets)
{
m *= set.size();
}
this.numElements = m;
}
@Override
public Iterator<List<T>> iterator()
{
return new Iterator<List<T>>()
{
/**
* The element counter
*/
private int current = 0;
/**
* The current combination
*/
private List<T> currentCombination = new ArrayList<T>();
/**
* The iterators over the individual sets
*/
private List<Iterator<? extends T>> subIterators =
new ArrayList<Iterator<? extends T>>(
Collections.<Iterator<? extends T>>nCopies(
sets.size(), null));
// Initialize the sub-iterators and the first combination
{
if (numElements > 0)
{
for (int i=0; i<sets.size(); i++)
{
Iterator<? extends T> subIterator =
sets.get(i).iterator();
subIterators.set(i, subIterator);
currentCombination.add(subIterator.next());
}
}
}
@Override
public boolean hasNext()
{
return current < numElements;
}
@Override
public List<T> next()
{
if (!hasNext())
{
throw new NoSuchElementException("No more elements");
}
List<T> result = new ArrayList<T>(currentCombination);
increase(sets.size()-1);
current++;
return result;
}
/**
* Increases the selection of elements by one.
*
* @param index The index to increase
*/
private void increase(int index)
{
if (index < 0)
{
return;
}
Iterator<? extends T> subIterator = subIterators.get(index);
if (subIterator.hasNext())
{
currentCombination.set(index, subIterator.next());
}
else
{
subIterator = sets.get(index).iterator();
subIterators.set(index, subIterator);
currentCombination.set(index, subIterator.next());
increase(index-1);
}
}
@Override
public void remove()
{
throw new UnsupportedOperationException(
"May not remove elements from a combination");
}
};
}
}
The usage of this class may look like this:
List<List<Integer>> inputs = new ArrayList<List<Integer>>();
input.add(Arrays.asList(0, 1, 2));
input.add(Arrays.asList(0, 1, 2, 3));
input.add(Arrays.asList(0, 1));
MixedRangeCombinationIterable<Integer> product =
new MixedRangeCombinationIterable(inputs)
for(List<Integer> combination: product){
System.out.println(combination)
}
