Generating all permutations, combinations, and power set of a string (2012)

Re:Generating all permutations, combinations, and power set ... by cpchen on Friday May 05, 2017 @12:36PM (#14274721)

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.

[ Parent | on HN ]

Re:Generating all permutations, combinations, and power set ... by daenz on Friday May 05, 2017 @03:08PM (#14276015)

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)

[ Parent | on HN ]

Re:Generating all permutations, combinations, and power set ... by bogomipz on Friday May 05, 2017 @02:03PM (#14275486)

Thanks for the good explanations. Cheers.

[ Parent | on HN ]