class CartesianProduct {

  public static <T> List<ArrayList<T>> cartesianProduct(List<List<T>> sets) throws Exception {
    final BigInteger MAX_LIST_SIZE = BigInteger.valueOf(100000);

    BigInteger productSize = BigInteger.ONE;
    for (List<T> set : sets) {
      productSize = productSize.multiply(BigInteger.valueOf(set.size()));
    }

    if (productSize.compareTo(MAX_LIST_SIZE) == 1) {
      throw new Exception("Will not generate carthesian product for more than " + MAX_LIST_SIZE
          + " elements " + "(size would be " + productSize + "). Not proceeding.");
    }

    List<ArrayList<T>> cartesianProduct = new ArrayList<ArrayList<T>>(productSize.intValue());
    for (int i = 0; i < productSize.intValue(); i++) {
      cartesianProduct.add(new ArrayList<T>(sets.size()));
    }
    
    if(productSize.equals(BigInteger.ZERO)) {
      // Empty product
      return cartesianProduct;
    }

    int loopSize = productSize.intValue();
    for (int i = 0; i < sets.size(); i++) {
      List<T> set = sets.get(i);

      loopSize /= set.size();
      Iterator<T> it = set.iterator();
      T e = null;
      for (int j = 0; j < productSize.intValue(); j++) {
        if ((j % loopSize) == 0) {
          if (it.hasNext()) {
            e = it.next();
          } else {
            it = set.iterator();
            e = it.next();
          }
        }

        cartesianProduct.get(j).add(e);
      }
    }

    return cartesianProduct;
  }

}

class CartesianProductTest {

  @Test
  public void testEmptyList() throws Exception {

    List<String> s1 = new ArrayList<String>();
    s1.add("a");
    s1.add("b");
    List<String> s2 = new ArrayList<String>();
    s2.add("c");
    s2.add("d");
    List<String> s3 = new ArrayList<String>();
    
    /*
     * s3 is empty, therefore the cartesian product should contain zero elements.
     * (i.e. you would not be able to satisfy the presentation policy in this case)
     */
    
    List<List<String>> l = new ArrayList<List<String>>();
    l.add(s1);
    l.add(s2);
    l.add(s3);
    
    List<ArrayList<String>> cp = CartesianProduct.cartesianProduct(l);
    
    List<List<String>> resultSet = new ArrayList<List<String>>();
    assertEquals(resultSet, cp);
  }

}