3 ms·
I guess if we're talking about this kind of powerset (because why not) a really, really simple way of generating all subsets of an N-element set is to iterate a
by ahelwer 12y ago
I guess if we're talking about this kind of powerset (because why not) a really, really simple way of generating all subsets of an N-element set is to iterate an int/long/whatever from 0 to (2^N)-1 and convert the bitmap at each step into a subset, where a 1 bit indicates inclusion and 0 bit indicates exclusion.
- sgk284 12y agoAlthough the powerset discussed in the article is different than the one being discussed here, the most elegant powerset construction I've ever seen uses a method similar to what you described but abstracted away by the List monad in Haskell. The full implementation is: powerset = filterM (const [True, False]) Which when ran will return: >>> powerset [1,2,3,4] [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]