Skip to content

Instantly share code, notes, and snippets.

@paradoja
Created November 5, 2012 03:15
Show Gist options
  • Save paradoja/4015132 to your computer and use it in GitHub Desktop.
Save paradoja/4015132 to your computer and use it in GitHub Desktop.
Compressed powerset
import Control.Monad
import Data.List
let unRoll = join .map (uncurry $ flip replicate)
let roll = map $ map (\l@(x:_) -> (x, length l)) . group:: [String] -> [[(Char, Int)]]
let powerSet = roll . nub . filterM (const [True, False]) . unRoll
powerSet [('a',2), ('b',2)]
import Control.Monad
import Data.List
powerSet = roll . nub . filterM (const [True, False]) . unRoll
unRoll = join .map (uncurry $ flip replicate)
roll :: [String] -> [[(Char, Int)]] -- monom. rest.
roll = map $ map (\l@(x:_) -> (x, length l)) . group
> powerSet [('a',2), ('b',2)]
[[('a',2),('b',2)],[('a',2),('b',1)],[('a',2)],[('a',1),('b',2)],[('a',1),('b',1)],[('a',1)],[('b',2)],[('b',1)],[]]
tochoGrande = map (map (\l@(x:_) -> (x, length l)) . group) . nub . filterM (const [True, False]) . join .map (uncurry $ flip replicate)
> tochoGrande [('a',2), ('b',2)]
[[('a',2),('b',2)],[('a',2),('b',1)],[('a',2)],[('a',1),('b',2)],[('a',1),('b',1)],[('a',1)],[('b',2)],[('b',1)],[]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment