Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
2010/11/12 Neil Toronto : > Jon Rafkind wrote: >> On 11/12/2010 02:25 PM, Eli Barzilay wrote: >>> >>> Any objections to `shuffle' in `racket/list'? > > No objections here. I will almost surely use this function in the future. > >> Dumb question but is this different from `shuffle-list' from games/cards ? > > Yes. The one in games/cards takes multiple shuffles to actually shuffle the > list. I think it's supposed to mimic physically shuffling a deck. Several shuffles are needed in order to make the the distribution uniform. If I recall correctly, Knuth, writes that you need 7 shuffles. -- Jens Axel _ 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?
Jon Rafkind wrote: On 11/12/2010 02:25 PM, Eli Barzilay wrote: Any objections to `shuffle' in `racket/list'? No objections here. I will almost surely use this function in the future. Dumb question but is this different from `shuffle-list' from games/cards ? Yes. The one in games/cards takes multiple shuffles to actually shuffle the list. I think it's supposed to mimic physically shuffling a deck. 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 11/12/2010 02:25 PM, Eli Barzilay wrote: > Any objections to `shuffle' in `racket/list'? > Dumb question but is this different from `shuffle-list' from games/cards ? _ 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?
Not by me. On Fri, Nov 12, 2010 at 2:25 PM, Eli Barzilay wrote: > Any objections to `shuffle' in `racket/list'? > > -- > ((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 > -- Jay McCarthy Assistant Professor / Brigham Young University http://faculty.cs.byu.edu/~jay "The glory of God is Intelligence" - D&C 93 _ 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?
Any objections to `shuffle' in `racket/list'? -- ((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?
10 minutes ago, Robby Findler wrote: > I think we want the one recommended by the statisticians. :) +1, not only because it's more robust, but there's the obvious benefit of adding a one-liner. > On Fri, Nov 12, 2010 at 2:36 PM, Jay McCarthy wrote: > > I think we should put in a list shuffler into the core. > > > > Which should we use? The faster one? -- ((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?
I think we want the one recommended by the statisticians. :) Robby On Fri, Nov 12, 2010 at 2:36 PM, Jay McCarthy wrote: > I think we should put in a list shuffler into the core. > > Which should we use? The faster one? > > Jay > > On Thu, Nov 11, 2010 at 11:26 AM, Eli Barzilay wrote: >> 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 >> > > > > -- > Jay McCarthy > Assistant Professor / Brigham Young University > http://faculty.cs.byu.edu/~jay > > "The glory of God is Intelligence" - D&C 93 > _ > 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?
I think we should put in a list shuffler into the core. Which should we use? The faster one? Jay On Thu, Nov 11, 2010 at 11:26 AM, Eli Barzilay wrote: > 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 > -- Jay McCarthy Assistant Professor / Brigham Young University http://faculty.cs.byu.edu/~jay "The glory of God is Intelligence" - D&C 93 _ 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 10:26 AM, Eli Barzilay wrote: > 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. http://en.wikipedia.org/wiki/Schwarzian_transform _ 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] 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?
Carl Eastlund wrote: On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto 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. Spanking good point, my good man. I think you're right. Just for the heck of it, I implemented the array-building version of Fisher-Yates and gave it a functional interface: (define (shuffle lst) (cond [(empty? lst) empty] [else (let* ([n (length lst)] [vec (make-vector n (first lst))]) (for ([e (in-list (rest lst))] [i (in-range 1 n)]) (define j (random (add1 i))) (vector-set! vec i (vector-ref vec j)) (vector-set! vec j e)) (vector->list vec))])) On my computer, it beats the sort-based shuffle on every list size I tried it on: 1, 5, 10, 100, and 1000. (Notably, not by much on length-10 lists.) It has better asymptotic complexity, so that should hold as the list size increases. Interestingly enough, it looks like O(n log n) is as good as purely functional code can get. The sorting version is downright elegant. (Well, it's not *purely* functional. But the Haskell people have to zip the list with random numbers in the Random monad, or some other such nonsense.) 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 11:40 AM, Carl Eastlund wrote: > On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto 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?
On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto 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?
Carl Eastlund wrote: On Thu, Nov 11, 2010 at 12:18 PM, Neil Toronto 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? 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. (I mean "proven," too. Distributions are very hard to establish using test cases.) Besides that, modern implementations of the Fisher-Yates shuffle are O(n), and this is O(n log n). Not a huge deal, but Fisher-Yates is simple enough that it's worth the cost to implement it once. 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?
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 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:18 PM, Neil Toronto 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?
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
[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
