Powerset construction in C#

http://bezensek.com/blog/2015/04/30/powerset-construction/

by MitjaBezensek • 11 years ago

29 7 11 years ago

carsongross2• 11 years ago

Believe 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• 11 years ago

Did you actually read the article? That's a different powerset.

carsongross2• 11 years ago

I did not, I have to admit.

ahelwer• 11 years 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• 11 years ago

Although 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],[]]

kazinator• 11 years ago

The 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• 11 years ago

Yeah I agree it can be confusing. Wikipedia uses both terms "the powerset construction or subset construction". http://en.wikipedia.org/wiki/Powerset_construction

Powerset construction in C#

Related Stories