4 ms·
Powerset construction in C#
- carsongross 11y agoBelieve it or not, I implemented powerset() as a joke in Gosu years ago: var set : java.util.Set<String> = {"a", "b", "c"} print( set.powerSet() ) prints [[], [b], [c], [b, c, a], [a], [b, c], [a, c], [b, a]] You can try it here (until the Heroku dyno goes down): http://gosu-lang.github.io/play.html
- btilly 11y agoDid you actually read the article? That's a different powerset.
- carsongross 11y agoI did not, I have to admit.
- ahelwer 11y agoI 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 11y 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],[]]
- deleted 11y ago[deleted]
- btilly 11y agoYou clearly didn't understand the article. The powerset construction you implemented turns a set into all subsets. The construction in the article turns one type of regular expression engine into another.
- deleted 11y ago[deleted]
- kazinator 11y agoThe terminology is a little confusing. It's better to call the NFA to DFA algorithm the "subset construction". The power set is a term which is used to denote the set of all subsets of a set. The states of a DFA are not all the possible subsets of the NFA; just those subsets which are generated by epsilon-closures on the state transitions. I.e. the set of DFA states consists of a subset of the power set of the NFA states.
- MitjaBezensek 11y agoYeah I agree it can be confusing. Wikipedia uses both terms "the powerset construction or subset construction". http://en.wikipedia.org/wiki/Powerset_construction http://en.wikipedia.org/wiki/Powerset_construction