[racket-dev] How about adding this simple list-shuffling procedure to racket?
I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list #:key (lambda (_) (random)) #:cache-keys? #t)) Thanks. _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
Eric Hanchrow wrote: I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list #:key (lambda (_) (random)) #:cache-keys? #t)) Is the distribution of shuffled lists uniform? That'd be hard to analyze, since it would depend on the sorting algorithm. I would guess it's not. (Don't worry if you didn't catch this yourself. It's not exactly straightforward.) If you want an unbiased shuffle, see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle Neil T _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
On Thu, Nov 11, 2010 at 12:18 PM, Neil Toronto neil.toro...@gmail.com wrote: Eric Hanchrow wrote: I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list #:key (lambda (_) (random)) #:cache-keys? #t)) Is the distribution of shuffled lists uniform? That'd be hard to analyze, since it would depend on the sorting algorithm. I would guess it's not. (Don't worry if you didn't catch this yourself. It's not exactly straightforward.) It should be uniform regardless of algorithm, since #:cache-keys? is #t. Shouldn't it? --Carl _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
I think that if random doesn't pick the same number twice you're guaranteed to be independent of the sorting algorithm, at least. Robby On Thu, Nov 11, 2010 at 11:18 AM, Neil Toronto neil.toro...@gmail.com wrote: Eric Hanchrow wrote: I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list #:key (lambda (_) (random)) #:cache-keys? #t)) Is the distribution of shuffled lists uniform? That'd be hard to analyze, since it would depend on the sorting algorithm. I would guess it's not. (Don't worry if you didn't catch this yourself. It's not exactly straightforward.) If you want an unbiased shuffle, see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle Neil T _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto neil.toro...@gmail.com wrote: I don't know. I know that the run through the list and swap with another random element algorithms are usually non-uniform, and so are a lot of other things that seem like they'd work. I wouldn't use something that wasn't proven to shuffle uniformly, at least for any serious statistics work. But this is not run through the list and swap with another random element. It's pick a random, uniform ordering, and then sort based on it. The random keys are chosen per element and cached (hence #:cache-keys? #t), not per comparison. --Carl _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
On Thu, Nov 11, 2010 at 11:40 AM, Carl Eastlund c...@ccs.neu.edu wrote: On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto neil.toro...@gmail.com wrote: I don't know. I know that the run through the list and swap with another random element algorithms are usually non-uniform, and so are a lot of other things that seem like they'd work. I wouldn't use something that wasn't proven to shuffle uniformly, at least for any serious statistics work. But this is not run through the list and swap with another random element. It's pick a random, uniform ordering, and then sort based on it. The random keys are chosen per element and cached (hence #:cache-keys? #t), not per comparison. Note that this is not the algorithm at the other end of the link that Neil T. sent; but one could probably make one like it in a simple manner using this idea. Robby _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
5 minutes ago, Neil Toronto wrote: Carl Eastlund wrote: It's pick a random, uniform ordering, and then sort based on it. The random keys are chosen per element and cached (hence #:cache-keys? #t), not per comparison. Spanking good point, my good man. I think you're right. It's a very common method, and the classic example of the decorate-map-strip method that has some perl-guy's name slapped on it now. The wikipedia page on FY is pretty decent -- and one concern that I've encountered in the past is that it's sensitive to what that page calls modulo bias. The decorated version is more robust, especially with (random) that works at the highest `random' granularity. (BTW, to compare them you should use some (random 1000) thing to avoid the fp cost.) -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://barzilay.org/ Maze is Life! _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
When truly picking uniformally shuffled lists from a given list, see: http://telefonica.net/web2/koot/natural-to-permutation.scm and try (require srfi/27) ; for random-integer (require natural-to-permutation.scm) (let* ((lst (build-list 1000 (lambda (k) (round (quotient k 10) (shuffler (make-K-P lst eq?)) (K (random-integer (nPs lst eq? (time (shuffler K))) Where random-integer is assumed to produce a uniform distribution. Jos _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] set operations
I think it is a good idea. Any objectors? Jay On Wed, Nov 10, 2010 at 12:40 PM, David Van Horn dvanh...@ccs.neu.edu wrote: The set library is missing a convenient way of selecting an element from a set, making it hard to write recursive functions matching the inductive structure of a set. Could you add this function, or something like it? (define (set-choose s) (let ((x (for/first ([x (in-set s)]) x))) (values x (set-remove s x David _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev -- Jay McCarthy j...@cs.byu.edu Assistant Professor / Brigham Young University http://faculty.cs.byu.edu/~jay The glory of God is Intelligence - DC 93 _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] set operations
I've written a version of `set-choose', and also `set-first' and `set-rest' (with the obvious meanings) a few times. They can be useful. (I always waffled about whether to use just `set-choose', or `set-first' along with `set-rest'. Mathematically, `set-first' and `set-rest' don't make sense, but they're easier to code with.) Neil T Ryan Culpepper wrote: I think a function named set-choose should return just the chosen element. I would call the function below set-split, maybe. Also, beware that for/first returns #f if the sequence is empty. Ryan On 11/11/2010 01:38 PM, Jay McCarthy wrote: I think it is a good idea. Any objectors? Jay On Wed, Nov 10, 2010 at 12:40 PM, David Van Horndvanh...@ccs.neu.edu wrote: The set library is missing a convenient way of selecting an element from a set, making it hard to write recursive functions matching the inductive structure of a set. Could you add this function, or something like it? (define (set-choose s) (let ((x (for/first ([x (in-set s)]) x))) (values x (set-remove s x David _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
[racket-dev] Something wrong with check-within
The check-within in the follow program (in BSL/ISL) seems to hang. This is sort of the simplest example I can reproduce, but my students have been running into this with some more complicated test cases. I thought it might have to do with the inexact numbers, but even if you change the #i0.501 to 0.501, it still hangs. I'm seeing this problem in version 5.0.2, but I believe my students are running 5.0.1... (define-struct anim (ctrl-pts curve-pts t running?)) (define SAMPLE-WORLD-NEXT (make-anim (list (make-posn 20 190) (make-posn 10 10) (make-posn 100 10) (make-posn 125 190) (make-posn 150 30)) (list (make-posn 20 190)) 0.501 true)) (check-within SAMPLE-WORLD-NEXT (make-anim (list (make-posn 20 190) (make-posn 10 10) (make-posn 100 10) (make-posn 125 190) (make-posn 150 30)) (list (make-posn 20 190)) #i0.501 true) 0.001) _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] Something wrong with check-within
On 11/11/10 7:34 PM, Nadeem Abdul Hamid wrote: The check-within in the follow program (in BSL/ISL) seems to hang. I see DrRacket (5.0.1, 5.0.99) loop on this: (check-within (make-posn (list 0) (list 0)) (make-posn (list 0) (list 0)) 0.001) David _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] Something wrong with check-within
submitted as bug report On Nov 11, 2010, at 7:54 PM, David Van Horn wrote: On 11/11/10 7:34 PM, Nadeem Abdul Hamid wrote: The check-within in the follow program (in BSL/ISL) seems to hang. I see DrRacket (5.0.1, 5.0.99) loop on this: _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
