Iterative Cartesian Product in Java

Question

Hi,

I want to compute the cartesian product of an arbitrary number of nonempty sets in Java.

I've wrote that iterative code...

public static <T> List<Set<T>> cartesianProduct(List<Set<T>> list) {
 List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size());
 List<T> elements = new ArrayList<T>(list.size());
 List<Set<T>> toRet = new ArrayList<Set<T>>();
 for (int i = 0; i < list.size(); i++) {
  iterators.add(list.get(i).iterator());
  elements.add(iterators.get(i).next());
 }
 for (int j = 1; j >= 0;) {
  toRet.add(Sets.newHashSet(elements));
  for (j = iterators.size()-1; j >= 0 && !iterators.get(j).hasNext(); j--) {
   iterators.set(j, list.get(j).iterator());
   elements.set(j, iterators.get(j).next());
  }
  elements.set(Math.abs(j), iterators.get(Math.abs(j)).next());
 }
 return toRet;
}

...but I found it rather inelegant. Someone has a better, still iterative solution? A solution that uses some wonderful functional-like approach? Otherwise... suggestion about how to improve it? Errors?

Thanks :)

Answer 1

You might be interested in Another question about cartesian products (edit: removed to conserve hyperlinks, search for the tag cartesian products). That answer has a nice recursive solution that I'd be hard pressed to improve on. Do you specifically want an iterative solution instead of recursive solution?

---

EDIT:

After looking at another iterative solution on stack overflow in perl and a clean explanation , here is another solution:

public static <T> List<Set<T>> uglyCartesianProduct(List<Set<T>> list) {
     List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size());
     List<T> elements = new ArrayList<T>(list.size());
     List<Set<T>> toRet = new ArrayList<Set<T>>();

     for (int i = 0; i < list.size(); i++) {
      iterators.add(list.get(i).iterator());
      elements.add(iterators.get(i).next());
     }

     for(int i = 0; i < numberOfTuples(list); i++)
     {
      toRet.add(new HashSet<T>());
     }

     int setIndex = 0;
     for (Set<T> set : list) {
      int index = 0;
      for (int i = 0; i < numberOfTuples(list); i++) {
       toRet.get(index).add((T) set.toArray()[index % set.size()]);
       index++;
      }
      setIndex++;
     }

     return toRet;
    }

    private static <T> int numberOfTuples(List<Set<T>> list) {
     int product = 1;
     for (Set<T> set : list) {
      product *= set.size();
     }
     return product;
    }

Answer 2

I believe this is correct. It is not seeking efficiency, but a clean style through recursion and abstraction.

The key abstraction is to introduce a simple Tuple class. This helps the generics later:

class Tuple<T> {
    private List<T> list = new ArrayList<T>();

    public void add(T t) { list.add(t); }

    public void addAll(Tuple<T> subT) {
        for (T t : subT.list) {
            list.add(t);
        }
    }

    public String toString() {
        String result = "(";

        for (T t : list) { result += t + ", "; }

        result = result.substring(0, result.length() - 2);
        result += " )";

        return result;
    } 
}

With this class, we can write a class like so:

public class Example {

public static <T> List<Tuple<T>> cartesianProduct(List<Set<T>> sets) {
    List<Tuple<T>> tuples = new ArrayList<Tuple<T>>();

    if (sets.size() == 1) {
        Set<T> set = sets.get(0);
        for (T t : set) {
            Tuple<T> tuple = new Tuple<T>();
            tuple.add(t);    
            tuples.add(tuple);
        }
    } else {
        Set<T> set = sets.remove(0);
        List<Tuple<T>> subTuples = cartesianProduct(sets);
        System.out.println("TRACER size = " + tuples.size());
        for (Tuple<T> subTuple : subTuples) {
            for (T t : set) {
                Tuple<T> tuple = new Tuple<T>();
                tuple.addAll(subTuple);
                tuple.add(t);
                tuples.add(tuple);
            }
        }
    }

    return tuples;
}

}

I have a decent example of this working, but it is omitted for brevity.

Answer 3

The following answer uses iteration and not recursion. It uses the same Tuple class from my previous answer.

It is a separate answer because IMHO both are valid, different approaches.

Here is the new main class:

public class Example {

    public static <T> List<Tuple<T>> cartesianProduct(List<Set<T>> sets) {
        List<Tuple<T>> tuples = new ArrayList<Tuple<T>>();

        for (Set<T> set : sets) {            
            if (tuples.isEmpty()) {
                for (T t : set) {
                    Tuple<T> tuple = new Tuple<T>();
                    tuple.add(t);    
                    tuples.add(tuple);
                }                
            } else {
                List<Tuple<T>> newTuples = new ArrayList<Tuple<T>>();

                for (Tuple<T> subTuple : tuples) {
                    for (T t : set) {
                        Tuple<T> tuple = new Tuple<T>();
                        tuple.addAll(subTuple);
                        tuple.add(t);
                        newTuples.add(tuple);
                    }
                }                

                tuples = newTuples;
            }
        }

        return tuples;
    }
}

Answer 4

I've written a solution that doesn't require you to fill up a large collection in memory. Unfortunately, the code required is hundreds of lines long. You may have to wait until it appears in the Guava project (http://guava-libraries.googlecode.com), which I hope will be by the end of the year. Sorry. :(

Note that you may not need such a utility if the number of sets you're cartesian-producting is a fixed number known at compile time -- you could just use that number of nested for loops.

EDIT: the code is released now.

Sets.cartesianProduct()

I think you'll be very happy with it. It only creates the individual lists as you ask for them; doesn't fill up memory with all MxNxPxQ of them.

If you want to inspect the source, it's here at line 727.

Enjoy!

Answer 5

Here is a lazy iterator approach that uses a function to produce an appropriate output type.

  public static <T> Iterable<T> cartesianProduct(
      final Function<Object[], T> fn, Object[]... options) {
    final Object[][] opts = new Object[options.length][];
    for (int i = opts.length; --i >= 0;) {
      // NPE on null input collections, and handle the empty output case here
      // since the iterator code below assumes that it is not exhausted the
      // first time through fetch.
      if (options[i].length == 0) { return Collections.emptySet(); }
      opts[i] = options[i].clone();
    }
    return new Iterable<T>() {
      public Iterator<T> iterator() {
        return new Iterator<T>() {
          final int[] pos = new int[opts.length];
          boolean hasPending;
          T pending;
          boolean exhausted;

          public boolean hasNext() {
            fetch();
            return hasPending;
          }

          public T next() {
            fetch();
            if (!hasPending) { throw new NoSuchElementException(); }
            T out = pending;
            pending = null;  // release for GC
            hasPending = false;
            return out;
          }

          public void remove() { throw new UnsupportedOperationException(); }

          private void fetch() {
            if (hasPending || exhausted) { return; }
            // Produce a result.
            int n = pos.length;
            Object[] args = new Object[n];
            for (int j = n; --j >= 0;) { args[j] = opts[j][pos[j]]; }
            pending = fn.apply(args);
            hasPending = true;
            // Increment to next.
            for (int i = n; --i >= 0;) {
              if (++pos[i] < opts[i].length) {
                for (int j = n; --j > i;) { pos[j] = 0; }
                return;
              }
            }
            exhausted = true;
          }
        };
      }
    };
  }