A library of combinatorial vector products in java
I'm looking for a Java library that can create 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 gives the number of dimensions (columns of combinations).
In Python, a function product
from a library intertools
does exactly that, but I haven't seen any Java library to do it.
Thank.
+3
source to share
4 answers
Below is a class that computes such a cross product, which is also called the Cartesian product of the input space. It is generalized to arbitrary data types and arbitrary number of dimensions.
( I originally posted it on GitHub , but now it's released here under the usual stackoverflow license)
It gets a list of collections in the constructor. Each of these collections provides an iterator that is used to iterate over the appropriate size. The whole class itself is implemented as Iterable
(basically just a wrapper for the corresponding class Iterator
). At any given time, this iterator maintains only a list of the "current" collection iterators and returns the corresponding elements and increments the iterators when called next()
.
The advantage of this approach is that it does not need to hold the entire Cartesian product in memory. Possibly iterating over a Cartesian product that is larger than the available physical memory (which might be important given that Cartesian products are getting large). In the meantime, there is no need to know about it. ”
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");
}
};
}
}
Using this class might look like:
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)
}
0
source to share
You can use java8 streams to do this in much the same way as if you were calling 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 output like this.
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 you either need to create a class for your pairs or use Tuple
+1
source to share
Solution # 1 . You can use a map to concatenate 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 is presented as follows:
Solution # 2 : you are creating a list of objects Combination
.
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 solution # 1, you can use Guava 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;
}
+1
source to share
Previous answers were good, but not generalizing for N dimensions.
This code is generic 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");
}
};
}
}
Typical use:
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)
}
0
source to share