There is a trivial bijective mapping from the power set of X = {A,B,C,D,E,F,G,H,I} to the set of numbers between 0 and 2^|X| = 2^9: Ø maps to 000000000 (base 2) {A} maps to 100000000 (base 2) {B} maps to 010000000 (base 2) {C} maps to 001000000 (base 2) … {I} maps to 000000001 (base … Read more
Power set of a set A is the set of all of the subsets of A. Not the most friendly definition in the world, but an example will help : Eg. for {1, 2}, the subsets are : {}, {1}, {2}, {1, 2} Thus, the power set is {{}, {1}, {2}, {1, 2}} To generate … Read more
Using STL: Permutation: using std::next_permutation template <typename T> void Permutation(std::vector<T> v) { std::sort(v.begin(), v.end()); do { std::copy(v.begin(), v.end(), std::ostream_iterator<T>(std::cout, ” “)); std::cout << std::endl; } while (std::next_permutation(v.begin(), v.end())); } Combination: template <typename T> void Combination(const std::vector<T>& v, std::size_t count) { assert(count <= v.size()); std::vector<bool> bitset(v.size() – count, 0); bitset.resize(v.size(), 1); do { for (std::size_t i … Read more
The fastest way is by using itertools, especially chain and combinations: >>> from itertools import chain, combinations >>> i = set([1, 2, 3]) >>> for z in chain.from_iterable(combinations(i, r) for r in range(len(i)+1)): print z () (1,) (2,) (3,) (1, 2) (1, 3) (2, 3) (1, 2, 3) >>> If you need a generator just … Read more
Just count 0 to 2^n – 1 and print the numbers according to the binary representation of your count. a 1 means you print that number and a 0 means you don’t. Example: set is {1, 2, 3, 4, 5} count from 0 to 31: count = 00000 => print {} count = 00001 => … Read more
Use this for creating the power set of x: function power(x, y) { var r = [y || []], // an empty set/array as fallback l = 1; for (var i=0; i<x.length; l=1<<++i) // OK, l is just r[i].length, but this looks nicer 🙂 for (var j=0; j<l; j++) { r.push(r[j].slice(0)); // copy r[j].push(x[i]); } … Read more
Recursion is your friend for this task. For each element – “guess” if it is in the current subset, and recursively invoke with the guess and a smaller superset you can select from. Doing so for both the “yes” and “no” guesses – will result in all possible subsets. Restraining yourself to a certain length … Read more
What’s in a powerset? A set’s subsets! An empty set is any set’s subset, so powerset of empty set’s not empty. Its (only) element it is an empty set: (define (powerset aL) (cond [(empty? aL) (list empty)] [else As for non-empty sets, there is a choice, for each set’s element, whether to be or not … Read more
Here is one more very elegant solution with no loops or recursion, only using the map and reduce array native functions. const getAllSubsets = theArray => theArray.reduce( (subsets, value) => subsets.concat( subsets.map(set => [value,…set]) ), [[]] ); console.log(getAllSubsets([1,2,3]));
You could apply a sequence the length of x over the m argument of the combn() function. x <- c(“red”, “blue”, “black”) do.call(c, lapply(seq_along(x), combn, x = x, simplify = FALSE)) # [[1]] # [1] “red” # # [[2]] # [1] “blue” # # [[3]] # [1] “black” # # [[4]] # [1] “red” “blue” … Read more