Mikkel Meyer Andersen |
February 24, 2011 at 18:32 (UTC) |
To tasks are quite common, especially writing math programs:
- Get a power set
- Partition a set into two in all possible ways
These two operations are of course interesting for Set<T> and cousins, but from a mathematical point of view, it is sufficient to solve this for index sets, i.e. sets {0, 1, ..., n - 1}. For List<T> and cousins (allowing duplicates), it can be a slightly different story depending on your view on the duplicates. So the rest of this post deals with index sets of size n, i.e. {0, 1, ..., n - 1}.
Especially for power sets, numerous implementations use strings. That I do not fancy. I tried to find implementations not using strings but merely used bitwise operations (which is also what the string using implementation does but they bring strings into the picture, maybe because it makes the programming a bit easier).
If you use some of this code in commercial software, you have to contact me first and make an agreement of usage. If your use is not commercial, feel free to use the code as long as you don't take credit for it yourself.
My implementations of the operations is shown below. Please contact me for questions or comments.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 | /** * 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(); } |
The usage is exemplified with the following example:
int[][][] pairs = Utils.getPairs(4); System.out.println(Utils.pairsToString(pairs)); int[][] powerset = Utils.getPowerset(4); System.out.println(Utils.powersetToString(powerset));
The output is:
(3), (2, 1, 0) (2), (3, 1, 0) (3, 2), (1, 0) (1), (3, 2, 0) (3, 1), (2, 0) (2, 1), (3, 0) (3, 2, 1), (0) 3 2 3, 2 1 3, 1 2, 1 3, 2, 1 0 3, 0 2, 0 3, 2, 0 1, 0 3, 1, 0 2, 1, 0 3, 2, 1, 0
