/**
 * Get the power set of {0, 1, ..., n}.
 * 
 * @param n the upper bound in the index set {0, 1, ..., n} to get the power set of
 * @return the powerset including the empty set and the set itself as the first and last element, respectively
 * @author Mikkel Meyer Andersen, scienco [at] mikl [dot] dk
 */
public static int[][] getPowerset(int n) {
    if (n <= 0) {
        throw new IllegalArgumentException("n must be be at least 1");
    }
 
    // stop at (2^n) - 1, so calculate 2^n
    final int stop = 1 << n;
 
    int i0 = 0, i1;
    int[][] powerset = new int[stop][];
 
    // Starting at i = 0 gives an empty first pair, so start at i = 1
    for (int i = 0; i < stop; ++i) {
        int j = i;
        int k = i;
 
        int size = 0;
 
        // First calculate size of the array needed
        for (int r = n - 1; r >= 0; --r) {
            if ((j & 1) == 1) {
                size++;
            }
 
            j >>>= 1;
        }
 
        i1 = 0;
        int[] set = new int[size];
 
        for (int r = n - 1; r >= 0; --r) {
            if ((k & 1) == 1) {
                set[i1++] = r;
            }
 
            k >>>= 1;
        }
 
        powerset[i0++] = set;
    }
 
    return powerset;
}
 
/**
 * Partition an index set {0, 1, ..., n} into two parts A and B such that A
 * union B is the whole set and A and B are disjoint. If you use this in
 * commercial software, do contact me first. If not, feel free to use this
 * code as long as you don't take credit for it yourself.
 * 
 * @param n the upper bound in the index set {0, 1, ..., n} to get pairs of
 * @return the pairs
 * @author Mikkel Meyer Andersen, scienco [at] mikl [dot] dk
 */
public static int[][][] getPairs(int n) {
    if (n <= 1) {
        throw new IllegalArgumentException(
                                           "n must be be at least 2 (it takes at least two elements to create a pair)");
    }
 
    // stop at 2^(n-1) - 1, so calculate 2^(n-1)
    final int stop = 1 << (n - 1);
 
    int i0 = 0, i1, i2;
    int[][][] pairs = new int[stop - 1][][];
 
    // Starting at i = 0 gives an empty first pair, so start at i = 1
    for (int i = 1; i < stop; ++i) {
        int j = i;
        int k = i;
 
        int size = 0;
 
        // First calculate size of the array needed
        for (int r = n - 1; r >= 0; --r) {
            if ((j & 1) == 1) {
                size++;
            }
 
            j >>>= 1;
        }
 
        i1 = 0;
        i2 = 0;
        int[] set1 = new int[size];
        int[] set2 = new int[n - size];
 
        for (int r = n - 1; r >= 0; --r) {
            if ((k & 1) == 1) {
                set1[i1++] = r;
            } else {
                set2[i2++] = r;
            }
 
            k >>>= 1;
        }
 
        pairs[i0++] = new int[][] {
            set1, set2
        };
    }
 
    return pairs;
}
 
/**
 * Formats the power set of {0, 1, ..., n} obtained by {@link getPowerset}
 * in a nicely looking string.
 * 
 * @param powerset the powerset to format nicely
 * @author Mikkel Meyer Andersen, scienco [at] mikl [dot] dk
 */
public static String powersetToString(int[][] powerset) {
    StringBuilder sb = new StringBuilder();
 
    for (int i = 0; i < powerset.length; ++i) {
        int[] set = powerset[i];
 
        for (int j = 0; j < set.length; ++j) {
            sb.append(set[j]);
 
            if (j < set.length - 1) {
                sb.append(", ");
            }
        }
 
        if (i < powerset.length - 1) {
            sb.append("\n");
        }
    }
 
    return sb.toString();
}
 
/**
 * Formats the different pairs partitioning the index set of {0, 1, ..., n}
 * obtained by {@link getPairs} in a nicely looking string.
 * 
 * @param pairs the pairs to format nicely
 * @author Mikkel Meyer Andersen, scienco [at] mikl [dot] dk
 */
public static String pairsToString(int[][][] pairs) {
    StringBuilder sb = new StringBuilder();
 
    for (int i = 0; i < pairs.length; ++i) {
        int[] set1 = pairs[i][0];
        int[] set2 = pairs[i][1];
 
        sb.append("(");
 
        for (int j = 0; j < set1.length; ++j) {
            sb.append(set1[j]);
 
            if (j < set1.length - 1) {
                sb.append(", ");
            }
        }
 
        sb.append("), (");
 
        for (int j = 0; j < set2.length; ++j) {
            sb.append(set2[j]);
 
            if (j < set2.length - 1) {
                sb.append(", ");
            }
        }
 
        sb.append(")");
 
        if (i < pairs.length - 1) {
            sb.append("\n");
        }
    }
 
    return sb.toString();
}