Re: Compare two methods of random permutations

Newsgroups	comp.programming
Date	2013-05-13 12:57 -0700
References	<kmegeh$921$1@news.albasani.net> <a79b56db-b5df-40f3-a764-390e42f65094@googlegroups.com> <kmrdpe$njc$1@news.albasani.net>
Message-ID	<6924f81f-a463-4cc2-a1f6-75fcb752fbc8@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 2:09:36 PM UTC-5, Mok-Kong Shen wrote:
> Am 13.05.2013 17:26, schrieb bob:
> 
> > Why would you not use the method of random permutation that is
> 
> > theoretically perfect?
> 
> 
> 
> It was my fault that I din't cross-post to 2 groups (thus I later
> 
> requested you to kindly look up there). I explained in sci.stat.math
> 
> my motivation as follows (note also that n=52 is only an example case):
> 
> 
> 
> ...... In particular I don't need to
> 
> generate the whole range of possible permutations but on the other hand
> 
> a not too limited small range. Consider the case n=52, one knows that
> 
> in-shuffle and out-shuffle have periods of 52 and 8 respectively, which
> 
> are negligibly small compared to the whole range (of size (52!)). On the
> 
> other hand, the method of Fisher and Yates needs n-1 (pseudo-)random
> 
> numbers. In one of my applications a couple of such random numbers are
> 
> already available for other reasons, so it would certainly be
> 
> conveninent and advantageous, if I could just use them for doing random
> 
> permutation without having to invoke a PRNG to acquire the n-1 random
> 
> numbers needed for F&Y. This was the motivation of my OP and, as it
> 
> turns out, my scheme runs also much faster than F&Y as reported further
> 
> below.
> 
> 
> 
> M. K. Shen

I think you may be overestimating the computational expense of creating pseudo-random numbers.  In general, it is not that expensive as this code from Java shows:

    /**
     * Returns a pseudo-random uniformly distributed {@code int} value of
     * the number of bits specified by the argument {@code bits} as
     * described by Donald E. Knuth in <i>The Art of Computer Programming,
     * Volume 2: Seminumerical Algorithms</i>, section 3.2.1.
     *
     * <p>Most applications will want to use one of this class' convenience methods instead.
     */
    protected synchronized int next(int bits) {
        seed = (seed * multiplier + 0xbL) & ((1L << 48) - 1);
        return (int) (seed >>> (48 - bits));
    }



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