4 ms·
There's a simple iterative alternative for generating power sets. For each item of a set, you will either include it or exclude it in one of the results. If you
by RodgerTheGreat 9y ago
There's a simple iterative alternative for generating power sets. For each item of a set, you will either include it or exclude it in one of the results. If you count from 0 to 2^n, the binary digits of your counter will enumerate every combination of these possibilities. In Java 8:
static <T> Set<Set<T>> power(List<T> a) {
return IntStream.range(0, 1 << a.size())
.mapToObj(x -> IntStream.range(0, a.size())
.filter(y -> (1 << y & x) != 0)
.mapToObj(y -> a.get(y))
.collect(Collectors.toSet())
).collect(Collectors.toSet());
}
In JS/ES6:
function power(a) {
var r = [];
for(var x = (1 << a.length) - 1; x >= 0; x--) {
r.push(a.filter((y, i) => 1 << i & x));
}
return r;
}
In K6:
{x@&:'+!(#x)#2}
- taeric 9y agoIf you enjoy this sort of thing, it is also the start of Knuth's volume 4. In it, he goes over many different schemes of generating things. My favorites are the ones he calls "loopless" since they do not have a loop during each iteration of the algorithm. So, in this example, there is no need for the filter line that will ultimately have to loop (or hash or something else not trivial) to find the items to filter out). In particular, to generate all permutations of binary digits requires something like 4 assignments and one test for each iteration. The ridiculously interesting ones are based on De Bruijn sequences. Basically, think if you have a combination lock that constantly shifts in 1 character when you type. Is it possible to test all combinations of digits without "wasting" a keypress?
- theoh 9y agoThe Wikipedia page for de Bruijn sequences is pretty good. https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence My personal interest is in generalized LFSRs, which can be used to generate de Bruijn sequences. From the wiki page for LFSR: "Non-binary Galois LFSR Binary Galois LFSRs like the ones shown above can be generalized to any q-ary alphabet {0, 1, ..., q − 1} (e.g., for binary, q = 2, and the alphabet is simply {0, 1}). In this case, the exclusive-or component is generalized to addition modulo-q (note that XOR is addition modulo 2), and the feedback bit (output bit) is multiplied (modulo-q) by a q-ary value, which is constant for each specific tap point. Note that this is also a generalization of the binary case, where the feedback is multiplied by either 0 (no feedback, i.e., no tap) or 1 (feedback is present). Given an appropriate tap configuration, such LFSRs can be used to generate Galois fields for arbitrary prime values of q."
- deleted 9y ago[deleted]
- bogomipz 9y ago>"For each item of a set, you will either include it or exclude it in one of the results." I found this interesting. This may be a silly question(my combinatorics knowledge is limited) but what exactly is the relationship between power sets and "N choose K"?
- cpchen 9y agoThe classic recurrence is if you're choosing K elements out of N, it either has the first element (in which case you choose K-1 elements out of the remaining N-1) or it doesn't (in which case you choose K elements out of the remaining N-1), so: N choose K = (N-1 choose K-1) + (N-1 choose K). Also, if you sum (N choose K) for all values of K you get 2^N.
- bogomipz 9y agoThanks for the good explanations. Cheers.
- daenz 9y agoI came at this from the perspective of the Binomial theorem: (x + y)^n = sum{k=0,n} (n choose k) x^(n-k) y^k And since a powerset is: sum{k=0,n} (n choose k) The way we can turn the first equation into a powerset is by setting x=1 and y=1, hence: 2^n = sum{k=0,n} (n choose k)
- bmm6o 9y agoThe combinations (n choose k) tell you how many ways there are to take k things from n, and so count that subset of the power set. And since the sets of k things are obviously distinct from the sets of j != k things, there is no overlap. This gives the well-known result that 2^n = Sum n choose k.
- mlpinit 9y agoAn example can be helpful: Given Set A = {1, 2, 3} This is the power Set of A P(A) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} (All the subsets of A including the empty set and A itself) 3 choose 2 = 3 (If you look in the power set, you'll see that there are only 3 ways to choose 2 items out of 3) Note that order does not matter.
- gwu78 9y agoHere is a spitbol/snobol4 solution. Assumes the number of items in the set is not greater than the alphabet. * routine stolen from gimpel * algorithm from peck and schrack define('p(s)t,n,c,k','p_init') :(p_end) p_init n = size(s) r = array('2:' n, 0) &alphabet len(n) . y x = array('2:' n, y) k = n + 1 p_0 k = k - 1 x[k] len(1) . s1 tab(k) . s2 = s2 s1 :s(p_0) define('p(s)i,k') p = s :(return) p k = size(s) p_1 s = replace(x[k],y,s) :f(p_2) r[k] = r[k] + 1 k = eq(remdr(r[k], k),0) k - 1 :s(p_1) p = s :(return) p_2 define('p(s)t,n,s1,s2','p_init') :(freturn) p_end * example: all permutations of string abcdefgh s = 'abcdefgh' abc output = p(s) :s(abc)f(end) end Here is another solution that only returns the unique permutations. The items of the set must first be sorted or grouped, e.g, a string like "cabcd" could be given as "ccabd", "adbcc", "abccd", etc. Duplicate items must be adjacent. define('r(s,ors)c,f,s1,a,d,os') :(r_end) r ors rtab(1) len(1) . c :f(freturn) s (span(c) | null) . f = s arb . s1 len(1) . d c = :f(r_1) r = s1 f c d s :(return) r_1 ors break(c) . os r = r(s,os) f :s(return)f(freturn) r_end s = 'abcdefgh' output = s x01 output = r(output,s) :s(x01) end