[racket-users] do loops
I try to fill a binary tree with 5 random numbers, avoiding duplicates. Is there a more elegant way than this (using "Iterations and Comprehensions")? (define tree4 (do ([x (random 10) (random 10)] [c #f (contains? tree x)] [tree null (if c tree (insert tree x))] [i 0 (if c i (add1 i))]) [(>= i 5) tree])) Thanks! -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] do loops
If your "insert" is idempotent, and you have some means of measuring tree size, you can eliminate i, c and x: (define tree4 (do ([tree null (insert tree (random 10))]) [(>= (tree-size tree) 5) tree])) I arrived at this by considering doing something similar for sets: (define tree4 (do ([tree (set) (set-add tree (random 10))]) [(>= (set-count tree) 5) tree])) On 2016-02-15 1:58 AM, JJ wrote: > I try to fill a binary tree with 5 random numbers, avoiding duplicates. Is > there a more elegant way than this (using "Iterations and Comprehensions")? > > (define tree4 > (do ([x (random 10) (random 10)] >[c #f (contains? tree x)] >[tree null (if c tree (insert tree x))] >[i 0 (if c i (add1 i))]) > [(>= i 5) tree])) > > Thanks! > -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] do loops
Or if you know that there are only 10 candidates, you can just iterate over (a prefix of) this list: (shuffle (build-list 10 values)) Robby On Mon, Feb 15, 2016 at 8:37 AM, Tony Garnock-Jones wrote: > If your "insert" is idempotent, and you have some means of measuring > tree size, you can eliminate i, c and x: > > (define tree4 > (do ([tree null (insert tree (random 10))]) > [(>= (tree-size tree) 5) tree])) > > I arrived at this by considering doing something similar for sets: > > (define tree4 > (do ([tree (set) (set-add tree (random 10))]) > [(>= (set-count tree) 5) tree])) > > > > On 2016-02-15 1:58 AM, JJ wrote: >> I try to fill a binary tree with 5 random numbers, avoiding duplicates. Is >> there a more elegant way than this (using "Iterations and Comprehensions")? >> >> (define tree4 >> (do ([x (random 10) (random 10)] >>[c #f (contains? tree x)] >>[tree null (if c tree (insert tree x))] >>[i 0 (if c i (add1 i))]) >> [(>= i 5) tree])) >> >> Thanks! >> > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] do loops
Right, but evaluating tree-size is O(n), even with a binary search tree. Doing this on each insertion is slow. The following is a possible solution without "do", and it only requires O(log n) on a (balanced) search tree: (define tree5 (let loop ([tree null] [n 5]) (define x (random 10)) (cond [(zero? n) tree] [(contains? tree x) (loop tree n)] [else (loop (insert tree x) (sub1 n))]))) But I thought there must be a more elegant solution using iterations and comprehensions. Thank you anyway! -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] do loops
> it only requires O(log n) on a (balanced) search tree: sorry, O(log n) for conttains? and O(n log n) in total -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
