How to get a list of all lists containing exactly

Question

As you may have understood with the title, I need some smart thinking here :)

I have a List<List<Object>> object. If you think of the Object objects as integers, you could see it like this :

{{1,2},{10,20,30},{100}}

I need to get all possible lists containing exactly one element of each list, that is, come up with this :

{{1,10,100},{1,20,100},{1,30,100},{2,10,100},{2,20,100},{2,30,100}}

Of course you don't know at compiling time how much items the lists will contain, so you cannot rely on an overlapping of for loops...

How would you come up with this? Time constraints are not relevant to my problem because the lists will likely contain few elements.

Answer 1

Just for completeness, what you are searching is called the Cartesian product of your lists, called such since the size of our result list is the product of the sizes of the individual lists.

---

Edit: Here is an implementation which works for arbitrary Iterables of Iterables, and creates an Iterable of lists. It creates the elements lazily on iteration, so it works for really big products which don't fit in the memory all at one, too.

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="http://stackoverflow.com/questions/5220701/how-to-get-a-list-of-all-lists-containing-exactly-one-element-of-each-list-of-a-l/5222370#5222370">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);
    }

}

---

One more edit: here is a index-based lazy list implementation.

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="http://stackoverflow.com/questions/5220701/how-to-get-a-list-of-all-lists-containing-exactly-one-element-of-each-list-of-a-l/5222370#5222370">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));
    }

}

I added implementations of contains, indexOf and lastIndexOf which are quite better than the original ones from AbstractList (or AbstractCollection) (for bigger factors than in your example, at least). These are not optimized for the sublists, since the sublists are simply taken from AbstractList.

Answer 2

You might use that scala code:

def xproduct (xx: List [List[_]]) : List [List[_]] = 
  xx match {
    case aa :: bb :: Nil => 
      aa.map (a => bb.map (b => List (a, b))).flatten       
    case aa :: bb :: cc => 
      xproduct (bb :: cc).map (li => aa.map (a => a :: li)).flatten
    case _ => xx
}

Since crossproduct is another name for cartesian product, it's name is xproduct.

Answer 3

Iterative algorithm.

public class A {
    public static List<List<Integer>> combinations(List<List<Integer>> inputList) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        for (Integer i : inputList.get(0)) {
            List<Integer> temp = new ArrayList<Integer>(1);
            temp.add(i);
            result.add(temp);
        }
        for (int i = 1; i < inputList.size(); i++) {
            result = make(result, inputList.get(i));
        }
        return result;
    }

    private static List<List<Integer>> make(List<List<Integer>> in, List<Integer> n) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        for (List<Integer> l : in) {
            for (Integer i : n) {
                List<Integer> cur = new ArrayList<Integer>(l.size() + 1);
                cur.addAll(l);
                cur.add(i);
                res.add(cur);
            }
        }
        return res;
    }
    public static void main(String[] args) {
        List<List<Integer>> inputList = new ArrayList();
        inputList.add(new ArrayList<Integer>() {{
            add(1);
            add(2);
        }});
        inputList.add(new ArrayList<Integer>() {{
            add(10);
            add(20);
            add(30);
        }});
        inputList.add(new ArrayList<Integer>() {{
            add(100);
        }});
        System.out.println(combinations(inputList));
    }
}

*Notice that this code not for production! You should replace LinkedList with ArrayList with initial size, make checks and so on.

upd usage example provided. there is some code improvement. But it still only draft. I wouldn't recommend you use it in real tasks.

Answer 4

I won't implement it, but here's an idea for a recursive algorithm:

• if we are dealing with a list containing a single list of elements (i.e.e.g {{1,2,3}}), then the result is - of course - a list of lists containing one element each (i.e.e.g. {{1},{2},{3}}
• if we have more than one list in the list of lists, we do a recursive call of the algorithm. We take all resulting lists from this recursive call and combine each element of the first list of the list of lists with each list from the recursive call.

Here's raw Python code:

def combiner(ll):
    if len(ll)==1:
        return [[x] for x in ll[0]] # base case
    firstlist = ll[0]
    result = []
    for i in combiner(ll[1:]): # recursive call
        for firstelem in firstlist:
            result.append([firstelem]+i) # combining lists
    return result

Answer 5

Here is a java implementation of phimuemue's Python algorithm.

private static List<List<Item>> getAllPossibleLists(List<List<Item>> itemsLists) {
    List<List<Item>> returned = new ArrayList<List<Item>>();
    if(itemsLists.size() == 1){
        for (Item item : itemsLists.get(0)) {
            List<Item> list = new ArrayList<Item>();
            list.add(item);
            returned.add(list);
        }
        return returned;
    }
    List<Item> firstList = itemsLists.get(0);
    for (List<Item> possibleList : getAllPossibleLists(itemsLists.subList(1, itemsLists.size()))) {
        for(Item firstItem : firstList){
            List<Item> addedList = new ArrayList<Item>();
            addedList.add(firstItem);
            addedList.addAll(possibleList);
            returned.add(addedList);
        }
    }
    return returned;
}

Feel free to comment further. Thank you for all your efforts !

Answer 6

Simple iterative algorithm.

    public static List<List<Object>> doStaff(List<List<Object>> objectList) {

        List<List<Object>> retList = new ArrayList<List<Object>>();

        int[] positions = new int[objectList.size()];
        Arrays.fill(positions,0);

        int idx = objectList.size() -1;
        int size = idx;

        boolean cont = idx > -1;

        while(cont) {

            idx = objectList.size() -1;

            while(cont && positions[idx] == objectList.get(idx).size()) {

                positions[idx] = 0;
                idx--;
                if(idx > -1) {
                    positions[idx] = positions[idx]+ 1;
                } else {
                    cont = false;
                }
            }

            if(cont) {
                List<Object> tmp = new ArrayList<Object>(size);
                for(int t = 0; t < objectList.size(); t++) {
                    tmp.add(t, objectList.get(t).get(positions[t]));
                    //System.out.print(objectList.get(t).get(positions[t])+ " ");
                }
                retList.add(tmp);
//              System.out.println();
                positions[size] = positions[size] + 1;
            }
        }
        return retList;
    }

If necessary, an explanation, just let me know.