Cartesian product combination

Cartesian product (卡氏積): All possible combination of the elements of  data sets.

Example:

X={A, B}

Y={C, D}

X × Y = {(A, C), (A, D), (B, C), (B, D)}

Code Snippet:

public class CartesianUtils {

  /**
   * Generate Cartesian product combination.
   * 
   * @param objects
   *            a list of arrays which are going to generate the Cartesian
   *            combination.
   * @return
   */
  public static Object[][] cartesianProduct(List products) {

    int productSize = products.size();

    Object[][] results;
    if (productSize > 0) {
      // Calculate the total combination of product sets
      int totalCombination = 1;
      for (int i = 0; i < productSize; i++) {
        totalCombination *= products.get(i).length;
      }

      results = new Object[totalCombination][productSize];

      // Store the element at the given index of the product
      Object[] elm = new Object[productSize];

      int productIndex = 0;

      int totalCombinationIndex = 0;

      // Store the index number of the product set
      int[] elmIndex = new int[productSize];
      // Initialize the index (except the last product set)
      for (int i = 0; i < productSize - 1; i++) {
        elmIndex[i] = 0;
      }

      do {
        if ((elmIndex[productIndex] < products.get(productIndex).length)
            && (productIndex < (productSize - 1))) {
          // Store the element at the given index if it is not the end
          // of the product set.
          Object[] obj = products.get(productIndex);
          elm[productIndex] = obj[elmIndex[productIndex]];
          productIndex++;
        } else {
          // Generate the result if it is the last product set
          if (productIndex == (productSize - 1)) {
            for (int i = 0; i < products.get(productIndex).length; i++) {
              // Retrieve the element of the previous
              // product sets
              for (int j = 0; j < productIndex; j++) {
                results[totalCombinationIndex][j] = elm[j];
              }
              // Retrieve all elements of the last product set
              results[totalCombinationIndex][productIndex] = products
                  .get(productIndex)[i];
              totalCombinationIndex++;
            }
          }

          // Move back to the previous product sets
          productIndex--;

          // End the loop if all the product sets have been processed.
          if (productIndex < 0) {
            break;
          }

          // Move to the next index of the product set
          elmIndex[productIndex]++;

          // Reset the index of the next product set
          elmIndex[productIndex + 1] = 0;

        }

      } while (true);

      return results;
    } else {
      return new Object[0][0];
    }
  }

  public static void main(String[] args) {
    List params = new ArrayList();
    params.add(new String[] { "A", "B" });
    params.add(new String[] { "C", "D" });

    Object[][] objects = CartesianUtils.cartesianProduct(params);

    System.out.println("Total combination: " + objects.length);

    for (int i = 0; i < objects.length; i++) {
      System.out.println("=======");
      for (int j = 0; j < objects[i].length; j++) {
        System.out.println(objects[i][j]);
      }
    }
  }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s