[deleted]
Generating all permutations, combinations, and power set of a string (2012)
31–40 of 48 posts
Re: Generating all permutations, combinations, and power set of a string (2012)
#32There'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 Set > power(List a) { return IntStream.range(0, 1 IntStream.range(0, a.size()) .filter(y -> (1 a.get(y)) .collect(Collectors.toSe…
>"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"?
An 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.
Re: Generating all permutations, combinations, and power set of a string (2012)
#33Earlier quoted context omitted.
>"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"?
The 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.
Thanks for the good explanations. Cheers.
Re: Generating all permutations, combinations, and power set of a string (2012)
#34Nice post. I don't know why there is no a bigger push in experiments/investigations with tree-like massive combinatorial expansion with lazy-evaluation, so the solution space can be somewhat "reasonable" (e.g. assuming you have infinite combinatorial expansion capability, adding restrictions, so once you start the evaluation most of the combinations get discarded, so you'll have to deal with a "sparse combinatorial expansion" analog to a convex space for solutions in geometry).
Re: Generating all permutations, combinations, and power set of a string (2012)
#35Earlier quoted context omitted.
>"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"?
The 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.
I 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)
Re: Generating all permutations, combinations, and power set of a string (2012)
#36In Haskell:
import Data.List ( subsequences )
powerset = subsequencesRe: Generating all permutations, combinations, and power set of a string (2012)
#37In Haskell: import Data.List ( subsequences ) powerset = subsequences
It doesn't contribute much to the conversation to note that your favorite language has a canned procedure for solving an algorithmic problem like this. If you're genuinely interested in demonstrating Haskell's capabilities it would be far more constructive to offer an implementation of such a routine, that it might be compared directly to the others in the article and this thread.
Re: Generating all permutations, combinations, and power set of a string (2012)
#38ha, fun.. I used to choke so much on powersets, after reading a lot I finally got the recursive version; here in python (I know, but I couldn't find back my lisp/ml version so..)
Re: Generating all permutations, combinations, and power set of a string (2012)
#39In Haskell: import Data.List ( subsequences ) powerset = subsequences
It doesn't contribute much to the conversation to note that your favorite language has a canned procedure for solving an algorithmic problem like this. If you're genuinely interested in demonstrating Haskell's capabilities it would be far more constructive to offer an implementation of such a routine, that it might be compared directly to the others in the article and this thread.
We'll have to agree to disagree.
Re: Generating all permutations, combinations, and power set of a string (2012)
#40There'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 Set > power(List a) { return IntStream.range(0, 1 IntStream.range(0, a.size()) .filter(y -> (1 a.get(y)) .collect(Collectors.toSe…
If 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)…
The Wikipedia page for de Bruijn sequences is pretty good. 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."