Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #1324

Re: Pseudorandom Permutation Algorithm for Arbitrary Size?

Cross-posted to 3 groups.

Show all headers | View raw

On 2/16/2012 4:47 AM, Andrew Tomazos wrote:
> Given a positive integer N, I would like a function f(N,i) where i is
> in [0,N) such that:
>
>      f(N,0) = x0
>      f(N,1) = x1
>      f(N,2) = x2
>      .
>      .
>      f(N,N-1) = x[N-1]
>
> where (x0, x1, x2, ..., x[N-1]) is a pseudo-random permutation of (0, 1,
> 2, .., N-1).
...
> - N may be very large, so allocating an identity permutation array and
> randomly shuffling it is out. Ideally calculating f(N,i) for some N
> and i should take constant size and space.

The problem here is that constant space eliminates any bookkeeping to
remember which elements have been used already.

>
> - If this is not possible than perhaps an easing constraint can be
> added that a stateful solution that guarantees f(N,i) will be called
> in ascending order of i values (ie f(N,0), f(N,1), f(N,2) and so on)
> would be useful to.

The usual shuffle algorithm can be written to produce its outputs in
that order. First it picks a random element from the entire list, and
swaps to put it in the first place, then it repeats the process on the
second through last elements ....

It takes O(N) space and time, but iteration i gives the value of element
i of the result, and each iteration takes constant time.

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