Re: Compare two methods of random permutations

Newsgroups	comp.programming
Date	2013-05-16 13:46 -0700
References	<kmegeh$921$1@news.albasani.net> <a79b56db-b5df-40f3-a764-390e42f65094@googlegroups.com> <33a7d2bf-c504-471a-b79e-93da93ef9e69@oy9g2000pbb.googlegroups.com>
Message-ID	<e2fc50f0-b70a-4c5e-a623-67becffdae83@googlegroups.com> (permalink)
Subject	Re: Compare two methods of random permutations
From	bob <bob@coolfone.comze.com>

Show all headers | View raw

On Monday, May 13, 2013 1:42:30 PM UTC-5, James Dow Allen wrote:
> On May 13, 10:26 pm, bob <b...@coolfone.comze.com> wrote:
> 
> > On Wednesday, May 8, 2013 4:35:18 PM UTC-5, Mok-Kong Shen wrote:
> 
> > > I want to compare in a practical sense two methods of random
> 
> >
> 
> > Why would you not use the method of random permutation that is theoretically perfect?  Isn't it pretty much trivial to implement and not very hard to understand?
> 
> 
> 
> Good question.  I'm going to guess he's worried about speed,
> 
> but still don't know how expects to improve on Fisher shuffle,
> 
> which only needs 51 small random integers for a 52-card deck.
> 
> 
> 
> Perhaps he doesn't know that you can get several independent
> 
> small integers from a single random-number, e.g. to get a
> 
> 12-permutation from a 31-bit random:
> 
> 
> 
>         int     a, b;
> 
>         do a = rand();
> 
>         while (a >= 1916006400);
> 
>         b = a % 12; a /= 12; doshufstep(12, b);
> 
>         b = a % 11; a /= 11; doshufstep(11, b);
> 
>         b = a % 10; a /= 10; doshufstep(10, b);
> 
>         b = a %  9; a /=  9; doshufstep( 9, b);
> 
>         b = a %  8; a /=  8; doshufstep( 8, b);
> 
>         b = a %  7; a /=  7; doshufstep( 7, b);
> 
>         b = a %  6; a /=  6; doshufstep( 6, b);
> 
>         b = a %  5; a /=  5; doshufstep( 5, b);
> 
>         b = a %  4; a /=  4; doshufstep( 4, b);
> 
>         b = a %  3; a /=  3; doshufstep( 3, b);
> 
>         b = a %  2; a /=  2; doshufstep( 2, b);
> 
> 
> 
> (A good compiler will remember the quotient
> 
> after doing the modulus.)
> 
> 
> 
> IIRC, I explained this to someone with a name
> 
> similar to OP's last decade.
> 
> 
> 
> James

I think what you are talking about is called "permutation unranking".

Basically, you take a number (a rank), and you use some math to convert it to a permutation.  Each rank corresponds to a unique permutation.

Thanks.

Thread

Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-08 23:35 +0200
  Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-11 21:31 -0700
    Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 08:07 +0200
      Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-13 02:34 -0700
  Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 08:01 +0200
  Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-13 08:26 -0700
    Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-13 11:42 -0700
      Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-16 13:46 -0700
    Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 21:09 +0200
      Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-13 12:57 -0700
        Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-13 22:59 +0200
          Re: Compare two methods of random permutations bob <bob@coolfone.comze.com> - 2013-05-13 15:28 -0700
            Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-14 10:54 +0200
              Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-14 05:32 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-14 22:46 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-14 14:19 -0700
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-14 15:06 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-15 10:16 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-15 03:54 -0700
                Re: Compare two methods of random permutations Patricia Shanahan <pats@acm.org> - 2013-05-15 07:11 -0700
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-15 11:04 -0700
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-15 11:06 -0700
                Re: Compare two methods of random permutations Patricia Shanahan <pats@acm.org> - 2013-05-15 12:55 -0700
                Re: Compare two methods of random permutations "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-05-16 06:10 +0100
                Re: Compare two methods of random permutations pacman@kosh.dhis.org (Alan Curry) - 2013-05-16 06:57 +0000
                Re: Compare two methods of random permutations "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-05-16 09:26 +0100
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-16 01:35 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-17 14:11 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-17 08:13 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 11:06 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 03:14 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 13:26 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 04:59 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 14:13 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 05:52 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 15:06 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 06:50 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 16:14 +0200
                Re: Compare two methods of random permutations James Dow Allen <jdallen2000@yahoo.com> - 2013-05-19 08:11 -0700
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 17:15 +0200
                Re: Compare two methods of random permutations Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-05-19 17:24 +0200

csiph-web