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
Yes, it is O(2^n) indeed, since you need to generate, well, 2^n possible combinations. Here’s a working implementation, using generics and sets: public static <T> Set<Set<T>> powerSet(Set<T> originalSet) { Set<Set<T>> sets = new HashSet<Set<T>>(); if (originalSet.isEmpty()) { sets.add(new HashSet<T>()); return sets; } List<T> list = new ArrayList<T>(originalSet); T head = list.get(0); Set<T> rest = new … Read more
The Python itertools page has exactly a powerset recipe for this: from itertools import chain, combinations def powerset(iterable): “powerset([1,2,3]) –> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)” s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) Output: >>> list(powerset(“abcd”)) [(), (‘a’,), (‘b’,), (‘c’,), (‘d’,), (‘a’, ‘b’), (‘a’, ‘c’), (‘a’, ‘d’), (‘b’, ‘c’), (‘b’, … Read more