Get cartesian product of dynimcally many sets defined by an array

Question

I want to get the Cartesian product of sets, that are defined by an array of upper bounds. For instance

int[] ub = [1,2]

describes the sets {0,1} and {0,1,2}. The Cartesian product is {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)}

For the lack of alternatives I wrote the following code that is really cumbersome and probably not efficient.

public static int[][] combineRecursive(int[] ub) {
    ArrayList<int[]> container = new ArrayList<int[]>();
    combineRecursive(new int[0], 0, ub, container);
    return container.toArray(new int[container.size()][]);
}

private static void combineRecursive(int[] node, int i, int[] ub, ArrayList<int[]> leafs) {
    if (i == ub.length) {
        leafs.add(node);
        return;
    }
    for (int val = 0; val <= ub[i]; val++) {
        int[] newNode = new int[node.length + 1];
        System.arraycopy(node, 0, newNode, 0, node.length);
        newNode[node.length] = val;
        combineRecursive(newNode, i + 1, ub, leafs);
    }
}

My questions are

1. Can I make that simpler and more importantly
2. Is there a library that does that kind of thing in 1 line.

Answer 1

I think there's an easier and more efficient way to construct your solution, given your exact problem.

You want to find the Cartesian product of items in a series of sequences described only by an upper-bound array - let's use your example of two upper-bounds [1,2] representing the two sequences {0,1},{0,1,2}.

To make it a bit simpler - let's assume also that there is no importance to order in the upper bounds - that the array [1,2] and the array [2,1] should bring us the same results.

In this case, you could simply take the highest number in the upper-bound array (which is 2) plus 1 to be the numeric base. We will now generate a series of numbers, and write to the array their base-3 representation. Not to worry, you do not have to know how to count in base 3 or make any special base-3 calculations. We are still decimal, using everyday numbers in this process. Just follow these steps:

1) order the upper bound array in ascending order. That would make comparing later on much simpler.

2) Calculte the base - the highest upper bound, plus 1.

3) calculate a number which is the upper bound of sequence we're creating. We will use this number is a loop later. It's calculated from right to left: base in the power of position, times the value in the position.

in the case of [1,2], the number will be 5: 3^0 * 2, plus 3^1 *1 ==> 2+3 ==>5.

4) going in a loop from 0 to 5 (the number found in the earlier step), look at Integer.toString(i, base). check if the base representation string is lower lexicographically than the upper bound. If so, add it as a result integer array.

And here's a code example.

public static void main(String[] args) {

  //step 1 - getting the array in sorted order, and adding a string representation.
  int[] upperBounds = {1,2};
  String upperBoundsStr = "12";
  int length = upperBounds.length;
  int base=0;
  Double rangeLimit=0.0;
  List<int[]> cartesianProduct = new ArrayList<int[]>();

  //step 2 - Find the base.
  for (int i=0;i<length;i++) {
      if (upperBounds[i]>base) {
          base=upperBounds[i];
      }
  }
  base++;

  //step 3 - Find the range limit
  for (int i=0;i<length;i++) {
      Double upperBoundsNum=new Double(upperBounds[length-i-1]*java.lang.Math.pow(base, i));
      rangeLimit+=upperBoundsNum;
  }

  //step 4 - Run over the range, and filter the non-relevant numbers
  for (int i=0;i<=rangeLimit.intValue();i++) {

      //Create a String representation of the number in the base. Add leading zeros.
      String number = Integer.toString(i, base);
      if (number.length()<upperBoundsStr.length()) {
          String leadingZero = "";
          for (int j=0;j<upperBoundsStr.length()-number.length();j++) {
              leadingZero+="0";
          }
          number=leadingZero+number;
      }

      //Compare the base representation to the upper bounds string, lexicographically.
      if (number.compareTo(upperBoundsStr)<=0) {
          char[] numberToAddChr= number.toCharArray();
          int[] numberToAdd = new int[numberToAddChr.length];
          for (int j=0;j<numberToAddChr.length;j++){
              numberToAdd[j] = (int) numberToAddChr[j];
          }
          cartesianProduct.add(numberToAdd);
      }
   }
}