Functionality to choose random, but unique, numbers. (Unfortunately, it doesn't appear to be nearly as fast as just checking randoms against a map) \begin{code} module RndUniq where import Random import Data.Set -- import Debug.Trace trace x e = e -- (Integral a, Random a, RandomGen g) => (a,a) -> g -> Int -> [a] urandomRs :: RandomGen g => (Int,Int) -> g -> Int -> [Int] urandomRs (mn,mx) g n = let rs = rnds g (mx-mn+1) in trace ("** rs= "++show rs) $(toList$ foldl (add_kth (mn,mx)) empty $take n rs) add_kth :: (Int,Int) -> Set Int -> Int -> Set Int add_kth range set k = trace ("Adding "++show k++"'th to set "++show (toList set))$ insert (find_value range k set) set rnds :: RandomGen g => g -> Int -> [Int] rnds g mx = if mx == 1 then [1] else let (r,g') = randomR (1,mx) g in r : rnds g' (mx-1) -- find the k'th value *not* in a set -- (the range is inclusive) find_value :: (Int,Int) -> Int -> Set Int -> Int find_value (mn,mx) k set = trace ("**"++show (mn,mx)++" : "++show (toList set)++" : "++show k) $if k <= 0 || k > mx-mn+1-(fromIntegral$ size set) then error ("k="++show k++" out of range ("++show mn++","++show mx++"),size="++show (size set)) else if Data.Set.null set then (mn+k-1) else let pivot = mn+(mx-mn) div 2 (left,piv,right) = splitMember pivot set -- sizes [mn..pivot-1][pivot][pivot+1..mx] empty_left = pivot - mn - (fromIntegral $size left) in trace ("** pivot: "++show pivot++" empty_left: "++show empty_left)$ case compare (empty_left+1) k of LT -> if piv then find_value (pivot+1,mx) (k-empty_left) right else find_value (pivot+1,mx) (k-empty_left-1) right EQ -> if piv then find_value (pivot+1,mx) 1 right else trace ("** Found: "++show pivot++"\n") pivot GT -> find_value (mn,pivot-1) k left \end{code}