All possible combination of n sets

Question

I have n Sets. Each Set has different number of elements. I would like to write an algorithm which give me all possible combinations from the sets. For example, let's say we have:

S1={1,2}, S2={A,B,C}, S3={$,%,£,!}

a combination should look like

C1={1,A,$}
C2={1,A,%}
...

...and so on. The number of possible combination will be 2*3*4 = 24

Please Help me to write this algorithm in Java.

Answer 1

Recursion is your friend:

public class PrintSetComb {
  public static void main(String[] args) {
    String[] set1 = {"1", "2"};
    String[] set2 = {"A", "B", "C"};
    String[] set3 = {"$", "%", "£", "!"};
    String[][] sets = {set1, set2, set3};

    printCombinations(sets, 0, "");
  }

  private static void printCombinations(String[][] sets, int n, String prefix) {
    if (n >= sets.length) {
      System.out.println("{" + prefix.substring(0, prefix.length() - 1) + "}");
      return;
    }
    for (String s : sets[n]) {
      printCombinations(sets, n + 1, prefix + s + ",");
    }
  }
}

In response to question from OP about generalizing it to sets of Objects:

public class PrintSetComb {
  public static void main(String[] args) {
    Integer[] set1 = {1, 2};
    Float[] set2 = {2.0F, 1.3F, 2.8F};
    String[] set3 = {"$", "%", "£", "!"};
    Object[][] sets = {set1, set2, set3};

    printCombinations(sets, 0, new Object[0]);
  }

  private static void printCombinations(Object[][] sets, int n, Object[] prefix) {
    if (n >= sets.length) {
      String outp = "{";
      for (Object o : prefix) {
        outp = outp + o.toString() + ",";
      }
      System.out.println(outp.substring(0, outp.length() - 1) + "}");
      return;
    }
    for (Object o : sets[n]) {
      Object[] newPrefix = Arrays.copyOfRange(prefix, 0, prefix.length + 1);
      newPrefix[newPrefix.length - 1] = o;
      printCombinations(sets, n + 1, newPrefix);
    }
  }
}

And finally an iterative variant. It is based on increasing an array of counters where the counter wraps and carries when it reaches the size of the set:

public class PrintSetCombIterative {
  public static void main(String[] args) {
    String[] set1 = {"1", "2"};
    String[] set2 = {"A", "B", "C"};
    String[] set3 = {"$", "%", "£", "!"};
    Object[][] sets = {set1, set2, set3};

    printCombinations(sets);
  }

  private static void printCombinations(Object[][] sets) {
    int[] counters = new int[sets.length];

    do {
      System.out.println(getCombinationString(counters, sets));
    } while (increment(counters, sets));
  }

  private static boolean increment(int[] counters, Object[][] sets) {
    for (int i = counters.length - 1; i >= 0; i--) {
      if (counters[i] < sets[i].length - 1) {
        counters[i]++;
        return true;
      } else {
        counters[i] = 0;
      }
    }
    return false;
  }

  private static String getCombinationString(int[] counters, Object[][] sets) {
    String combo = "{";
    for (int i = 0; i < counters.length; i++) {
      combo = combo + sets[i][counters[i]] + ",";
    }
    return combo.substring(0, combo.length() - 1) + "}";
  }
}

Answer 2

In the case someone wants the matrix instead of printing, I slightly modified the code:

public class TestSetCombinations2 {
  public static void main(String[] args) {
    Double[] set1 = {2.0, 3.0};
    Double[] set2 = {4.0, 2.0, 1.0};
    Double[] set3 = {3.0, 2.0, 1.0, 5.0};
    Double[] set4 = {1.0, 1.0};
    Object[][] sets = {set1, set2, set3, set4};

    Object[][] combinations = getCombinations(sets);

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

  private static Object[][] getCombinations(Object[][] sets) {
    int[] counters = new int[sets.length];
    int count = 1;
    int count2 = 0;

    for (int i = 0; i < sets.length; i++) {
      count *= sets[i].length;
    }

    Object[][] combinations = new Object[count][sets.length];

    do {
      combinations[count2++] = getCombinationString(counters, sets);
    } while (increment(counters, sets));

    return combinations;
  }

  private static Object[] getCombinationString(int[] counters, Object[][] sets) {
    Object[] o = new Object[counters.length];
    for (int i = 0; i < counters.length; i++) {
      o[i] = sets[i][counters[i]];
    }
    return o;
  }

  private static boolean increment(int[] counters, Object[][] sets) {
    for (int i = counters.length - 1; i >= 0; i--) {
      if (counters[i] < sets[i].length - 1) {
        counters[i]++;
        return true;
      } else {
        counters[i] = 0;
      }
    }
    return false;
  }
}