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)) { 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; }  static List<ArrayList<T>> cartesianProduct(List<List<T>> sets);  }
@Test public void testEqualySizedLists() 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.add("e"); s3.add("f"); 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>>(); List<String> rl = new ArrayList<String>(); rl.add("a"); rl.add("c"); rl.add("e"); resultSet.add(rl); rl = new ArrayList<String>(); rl.add("a"); rl.add("c"); rl.add("f"); resultSet.add(rl); rl = new ArrayList<String>(); rl.add("a"); rl.add("d"); rl.add("e"); resultSet.add(rl); rl = new ArrayList<String>(); rl.add("a"); rl.add("d"); rl.add("f"); resultSet.add(rl); rl = new ArrayList<String>(); rl.add("b"); rl.add("c"); rl.add("e"); resultSet.add(rl); rl = new ArrayList<String>(); rl.add("b"); rl.add("c"); rl.add("f"); resultSet.add(rl); rl = new ArrayList<String>(); rl.add("b"); rl.add("d"); rl.add("e"); resultSet.add(rl); rl = new ArrayList<String>(); rl.add("b"); rl.add("d"); rl.add("f"); resultSet.add(rl); assertEquals(resultSet, cp); }
@Test public void testUnequalySizedLists() throws Exception { List<String> s1 = new ArrayList<String>(); s1.add("a"); s1.add("b"); List<String> s2 = new ArrayList<String>(); s2.add("c"); List<String> s3 = new ArrayList<String>(); s3.add("e"); s3.add("f"); 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>>(); List<String> rl = new ArrayList<String>(); rl.add("a"); rl.add("c"); rl.add("e"); resultSet.add(rl); rl = new ArrayList<String>(); rl.add("a"); rl.add("c"); rl.add("f"); resultSet.add(rl); rl = new ArrayList<String>(); rl.add("b"); rl.add("c"); rl.add("e"); resultSet.add(rl); rl = new ArrayList<String>(); rl.add("b"); rl.add("c"); rl.add("f"); resultSet.add(rl); assertEquals(resultSet, cp); }
@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>(); 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); }
@Test public void testEmpty() throws Exception { List<List<String>> l = new ArrayList<List<String>>(); List<ArrayList<String>> cp = CartesianProduct.cartesianProduct(l); List<List<String>> resultSet = new ArrayList<List<String>>(); resultSet.add(new ArrayList<String>()); assertEquals(resultSet, cp); }
@Test public void testTooLarge() throws Exception { final int PRODUCT_ELEMENTS = 100; List<List<String>> l = new ArrayList<List<String>>(); for (int i=0;i<PRODUCT_ELEMENTS;++i) { List<String> s1 = new ArrayList<String>(); s1.add("a"); s1.add("b"); l.add(s1); } try { CartesianProduct.cartesianProduct(l); fail("Expected exception"); } catch(Exception ex) { assertTrue(ex.getMessage().contains(BigInteger.valueOf(2).pow(PRODUCT_ELEMENTS).toString())); } }