Просто для полноты то, что вы ищете, называется декартовым произведением ваших списков, которое называется таковым, поскольку размер нашего списка результатов является произведением размеров отдельных списков.
Edit: вот реализация, которая работает для произвольных Iterables of Iterables и создает Iterable из списков. Он лениво создает элементы на итерации, поэтому он работает для действительно больших продуктов, которые тоже не помещаются в памяти одновременно.
package de.fencing_game.paul.examples;
import java.util.*;
/**
* A iterable over the cartesian product of a iterable of iterables
* with some common element type.
*<p>
* The elements of the product are tuples (lists) of elements, one of
* each of the original iterables.
*<p>
* The iterator iterates the elements in lexicographic order, ordered by
* the appearance of their components in their respective iterators.
*<p>
* Since we are iterating the iterables lazily, the iterators should
* act the same each time, otherwise you'll get strange results (but it
* will still be well-defined).
*</p>
*
* Inspired by the question <a href="/4999631/kak-poluchit-spisok-vseh-spiskov-soderzhaschih-rovno-odin-element-kazhdogo-spiska-iz-spiska-spiskov">How to get a list of all lists containing exactly one element of each list of a list of lists</a> on Stackoverflow (by Dunaril).
*
* @author Paŭlo Ebermann
*/
public class ProductIterable<X>
implements Iterable<List<X>>
{
private Iterable<? extends Iterable<? extends X>> factors;
public ProductIterable(Iterable<? extends Iterable<? extends X>> factors) {
this.factors = factors;
}
public Iterator<List<X>> iterator() {
return new ProductIterator();
}
private class ProductIterator
implements Iterator<List<X>>
{
/**
* an element of our stack, which contains
* an iterator, the last element returned by
* this iterator, and the Iterable which created
* this iterator.
*/
private class StackElement {
X item;
Iterator<? extends X> iterator;
Iterable<? extends X> factor;
boolean has;
StackElement(Iterable<? extends X> fac) {
this.factor = fac;
newIterator();
}
/**
* checks whether the {@link #step} call can
* get a new item.
*
*/
boolean hasNext() {
return has ||
(has = iterator.hasNext());
}
/**
* steps to the next item.
*/
void step() {
item = iterator.next();
has = false;
}
/**
* creates a new iterator.
*/
void newIterator() {
iterator = factor.iterator();
has = false;
}
/**
* for debugging: a string view of this StackElement.
*/
public String toString() {
return "SE[ i: " + item + ", f: " + factor + "]";
}
}
/**
* our stack of iterators to run through
*/
private Deque<StackElement> stack;
/**
* is our next element already produced (= contained in
* the `item`s of the stack?
*/
private boolean hasNext;
/**
* constructor.
*/
ProductIterator() {
stack = new ArrayDeque<StackElement>();
try {
fillStack();
hasNext = true;
}
catch(NoSuchElementException ex) {
hasNext = false;
}
}
/**
* creates the stack. only called from constructor.
*/
private void fillStack() {
for(Iterable<? extends X> fac : factors) {
StackElement el = new StackElement(fac);
el.step();
stack.push(el);
}
}
/**
* steps the iterator on top of the stack, and maybe the iterators
* below, too.
* @return true if more elements are available.
*/
private boolean stepIterator() {
if(stack.isEmpty())
return false;
StackElement top = stack.peek();
while(!top.hasNext()) {
stack.pop();
if (!stepIterator()) {
return false;
}
top.newIterator();
stack.push(top);
}
top.step();
return true;
}
/**
* returns true if `next` will return a next element.
*/
public boolean hasNext() {
return
hasNext ||
(hasNext = stepIterator());
}
/**
* returns the next element of the cartesian product.
*/
public List<X> next() {
if(!hasNext()) {
throw new NoSuchElementException();
}
hasNext = false;
return makeList();
}
/**
* creates a list from the StackElements in reverse order.
*/
private List<X> makeList() {
List<X> list = new ArrayList<X>(stack.size());
// TODO: more efficient reverse copying
for(StackElement se : stack) {
list.add(0, se.item);
}
return list;
}
/**
* the remove method is not supported,
* the cartesian product is immutable.
*/
public void remove() {
throw new UnsupportedOperationException();
}
} // class ProductIterator
/**
* a test method which creates a list of lists and
* from this the cartesian product.
*/
public static void main(String[] params) {
@SuppressWarnings("unchecked")
List<List<Integer>> factors =
Arrays.asList(Arrays.asList(1,2),
Arrays.asList(10,20,30),
Arrays.asList(100));
Iterable<List<Integer>> product =
new ProductIterable<Integer>(factors);
List<List<Integer>> productList =
new ArrayList<List<Integer>>();
for(List<Integer> pEl : product) {
productList.add(pEl);
System.out.println(pEl);
}
System.out.println(productList);
}
}
Еще одно редактирование: вот реализация на основе индекса с отложенным списком.
package de.fencing_game.paul.examples;
import java.util.*;
/**
* The cartesian product of lists, in an (unmodifiable) index-based
* implementation.
*
*<p>
* The elements of the product are tuples (lists) of elements, one from
* each of the base list's element lists.
* These are ordered in lexicographic order, by their appearance in the
* base lists.
*</p>
*<p>
* This class works lazily, creating the elements of the product only
* on demand. It needs no additional memory to the base list.
*</p>
*<p>
* This class works even after changes of the base list or its elements -
* the size of this list changes if any of the factor lists changes size.
* Such changes should not occur during calls to this method, or
* you'll get inconsistent results.
*</p>
* <p>
* The product of the sizes of the component lists should be smaller than
* Integer.MAX_INT, otherwise you'll get strange behaviour.
* </p>
*
*<p>
* Inspired by the question <a href="/4999631/kak-poluchit-spisok-vseh-spiskov-soderzhaschih-rovno-odin-element-kazhdogo-spiska-iz-spiska-spiskov">How to get a list of all lists containing exactly one element of each list of a list of lists</a> on Stackoverflow (by Dunaril).
*
* @author Paŭlo Ebermann
*/
public class ProductList<X>
extends AbstractList<List<X>>
{
private List<? extends List<? extends X>> factors;
/**
* create a new product list, based on the given list of factors.
*/
public ProductList(List<? extends List<? extends X>> factors) {
this.factors = factors;
}
/**
* calculates the total size of this list.
* This method takes O(# factors) time.
*/
public int size() {
int product = 1;
for(List<?> l : factors) {
product *= l.size();
}
return product;
}
/**
* returns an element of the product list by index.
*
* This method calls the get method of each list,
* so needs needs O(#factors) time if the individual
* list's get methods are in O(1).
* The space complexity is O(#factors), since we have to store
* the result somewhere.
*
* @return the element at the given index.
* The resulting list is of fixed-length and after return independent
* of this product list. (You may freely modify it like an array.)
*/
public List<X> get(int index) {
if(index < 0)
throw new IndexOutOfBoundsException("index " + index+ " < 0");
// we can't create a generic X[], so we take an Object[]
// here and wrap it later in Arrays.asList().
Object[] array = new Object[factors.size()];
// we iteratively lookup the components, using
// modulo and division to calculate the right
// indexes.
for(int i = factors.size() - 1; i >= 0; i--) {
List<?> subList = factors.get(i);
int subIndex = index % subList.size();
array[i] = subList.get(subIndex);
index = index / subList.size();
}
if(index > 0)
throw new IndexOutOfBoundsException("too large index");
@SuppressWarnings("unchecked")
List<X> list = (List<X>)Arrays.asList(array);
return list;
}
/**
* an optimized indexOf() implementation, runs in
* O(sum n_i) instead of O(prod n_i)
* (if the individual indexOf() calls take O(n_i) time).
*
* Runs in O(1) space.
*/
public int indexOf(Object o)
{
if(!(o instanceof List))
return -1;
List<?> list = (List<?>)o;
if (list.size() != factors.size())
return -1;
int index = 0;
for(int i = 0; i < factors.size(); i++) {
List<?> subList = factors.get(i);
Object candidate = list.get(i);
int subIndex = subList.indexOf(candidate);
if(subIndex < 0)
return -1;
index = index * subList.size() + subIndex;
}
return index;
}
/**
* an optimized lastIndexOf() implementation, runs in
* O(sum n_i) time instead of O(prod n_i) time
* (if the individual indexOf() calls take O(n_i) time).
* Runs in O(1) space.
*/
public int lastIndexOf(Object o)
{
if(!(o instanceof List))
return -1;
List<?> list = (List<?>)o;
if (list.size() != factors.size())
return -1;
int index = 0;
for(int i = 0; i < factors.size(); i++) {
List<?> subList = factors.get(i);
Object candidate = list.get(i);
int subIndex = subList.lastIndexOf(candidate);
if(subIndex < 0)
return -1;
index = index * subList.size() + subIndex;
}
return index;
}
/**
* an optimized contains check, based on {@link #indexOf}.
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/**
* a test method which creates a list of lists and
* shows the cartesian product of this.
*/
public static void main(String[] params) {
@SuppressWarnings("unchecked")
List<List<Integer>> factors =
Arrays.asList(Arrays.asList(1,2),
Arrays.asList(10,20,30, 20),
Arrays.asList(100));
System.out.println("factors: " + factors);
List<List<Integer>> product =
new ProductList<Integer>(factors);
System.out.println("product: " + product);
List<Integer> example = Arrays.asList(2,20,100);
System.out.println("indexOf(" + example +") = " +
product.indexOf(example));
System.out.println("lastIndexOf(" + example +") = " +
product.lastIndexOf(example));
}
}
Я добавил реализации contains, indexOf и lastIndexOf, которые намного лучше оригинальных из AbstractList (или AbstractCollection) (по крайней мере, для более значительных факторов, чем в вашем примере). Они не оптимизированы для подсписков, поскольку подсписки просто взяты из AbstractList.