Re: Pseudorandom Permutation Algorithm for Arbitrary Size?

Path	csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date	Thu, 16 Feb 2012 10:39:34 -0600
Date	Thu, 16 Feb 2012 08:39:09 -0800
From	Patricia Shanahan <pats@acm.org>
User-Agent	Thunderbird 1.5.0.2 (Windows/20060308)
MIME-Version	1.0
Newsgroups	comp.theory, sci.math, comp.programming
Subject	Re: Pseudorandom Permutation Algorithm for Arbitrary Size?
References	<dfb9f176-c69c-4960-9cdd-f53f805b230c@z31g2000vbt.googlegroups.com> <jhj69p$u9g$1@news.albasani.net>
In-Reply-To	<jhj69p$u9g$1@news.albasani.net>
Content-Type	text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding	8bit
Message-ID	<OYGdnXTpW9LbrKDSnZ2dnUVZ_qCdnZ2d@earthlink.com> (permalink)
Lines	11
X-Usenet-Provider	http://www.giganews.com
NNTP-Posting-Host	70.230.206.198
X-Trace	sv3-jAQ0no+D8WhT/MmeabN+ywZD8+SNI+tNUJBiSIYJeJh3mVRHO/DuB56Qd+QV/rNZEIYX4QYHVx6WRMt!uHjO8AlJxw21f/Ky9gRhwadcTz5EX6s10h/eqqdpA5jmXTT/8Cepapl9stA/cMTGWUBqnGeftkbp!9sGdNvCeA9pbBgHPFDJ1st7daY9u+NoCZSyg7Ypbpmd3/NU=
X-Abuse-and-DMCA-Info	Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info	Otherwise we will be unable to process your complaint properly
X-Postfilter	1.3.40
X-Original-Bytes	1619
Xref	x330-a1.tempe.blueboxinc.net comp.theory:2140 comp.programming:1328

Cross-posted to 3 groups.

Show key headers only | View raw

root wrote:
...
> Generate an array of N random numbers. Generate a second array
> of numbers from 0 to N-1, in order. Sort the first array
> in ascending order while simultaneously re-arranging the
> second array to maintain its relation to the first array.
> Use the resulting second array to index your data.

This uses even more memory than the Fisher–Yates shuffle.

Patricia

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Pseudorandom Permutation Algorithm for Arbitrary Size? Andrew Tomazos <andrew@tomazos.com> - 2012-02-16 04:47 -0800
  Re: Pseudorandom Permutation Algorithm for Arbitrary Size? Patricia Shanahan <pats@acm.org> - 2012-02-16 06:22 -0800
  Re: Pseudorandom Permutation Algorithm for Arbitrary Size? James Dow Allen <jdallen2000@yahoo.com> - 2012-02-16 06:57 -0800
  Re: Pseudorandom Permutation Algorithm for Arbitrary Size? root <NoEMail@home.org> - 2012-02-16 15:10 +0000
    Re: Pseudorandom Permutation Algorithm for Arbitrary Size? Patricia Shanahan <pats@acm.org> - 2012-02-16 08:39 -0800
  Re: Pseudorandom Permutation Algorithm for Arbitrary Size? rossum <rossum48@coldmail.com> - 2012-02-16 15:24 +0000

csiph-web