Am 20.07.2012 15:24, schrieb jwaldmann:
Dear all,
how would I quickly select an element of a Set (as in Data.Set) uniformly at random?
If you use a "Map a ()" (or Map a a) you can use Map.elemAt. The initial conversion is still linear, though. -- | convert a set into an identity map setToMap :: Ord a => Set.Set a -> Map.Map a a setToMap = Map.fromDistinctAscList . List.map (\ a -> (a, a)) . Set.toList HTH C.
Via the API, this can only be done in linear time? (via toList) If I could access the tree structure, then of course it could be logarithmic.
But probably I'd need a weighted selection sooner or later, and this would require some specific code anyway. Or does it not?
Actually I need a sequence of such selections (each selected element is deleted immediately). I don't need all elements (so, computing a random permuation might be too much).
J.W.