On Thu, 19 Nov 2009 01:13:23 +0100 Henning Thielemann <[email protected]> wrote:
HT> Ted Zlatanov schrieb: >> On Mon, 16 Nov 2009 00:03:54 +0300 Eugene Kirpichov <[email protected]> >> wrote: >> EK> 2009/11/15 Michael Mossey <[email protected]>: >>>> Can someone tell me if this is correct. I'm guessing that if I represent >>>> two sets of integers by Word32 (where ith bit set means i is in the set), >>>> then an algorithm to determine if x is a subset of y would go something >>>> like >>>> >>>> >>>> (y - x) == (y `exclusiveOr` x) >> EK> It's simpler: "x&~y == 0" >> >> Depending on the OP data set the simple bit vector may be a good >> strategy, but I wonder if an inversion list would be better? Do you >> expect long runs of adjacent numbers and gaps? Inversion lists tend to >> encode those much more efficiently than bit vectors. >> >> I'm just now learning Haskell so I don't know enough to show an >> implementation but inversion lists are very simple conceptually. If >> your set is (2,3,4,5,8,9,10) the inversion list would be (2,6,8,11). >> It's easy to generate it from a set of Ord elements. HT> Is "inversion list" = "Gray code" ? No. An inversion list contains the boundaries of all the continuous intervals in the input. In other words, any time you see input of [n,n+1, n+2...n+k,n+m...] where m > k+1 your inversion list gets the entries n and n+k+1. As I said I'm just starting to learn Haskell so I can't give a proper implementation: isSuccessor:: (Num a) => a -> a -> Bool isSuccessor x y = x+1 == y inversion :: (Num a) => [a] -> [a] inversion [] = [] inversion (x:xs) = x:(inversion . dropWhile isSuccessor xs) The above is obviously broken, but the idea is to drop successive elements. I don't know how to do that in a predicate for dropWhile so I may need a different function from Data.List or elsewhere. Ted _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
