| Author |
Message |
Christopher V. Kimball
science forum beginner
Joined: 21 Sep 2005
Posts: 4
|
 Posted: Wed Sep 21, 2005 5:50 pm Post subject:
Efficient generation of random permutations from random bit streams.
|
|
|
Can a random permutation of N objects be constructed from log2( N!) +1
random bits?
The methods I'm aware of are inefficient relative to the log2(N!) limit. |
|
| Back to top |
|
 |
Christopher V. Kimball
science forum beginner
Joined: 21 Sep 2005
Posts: 4
|
| Posted: Wed Sep 21, 2005 9:11 pm Post subject:
Re: Efficient generation of random permutations from random bit streams.
|
|
|
Is a "factorial base" decomposition unique?
Practically, such a decomposition would be difficult even for N=52 on
today's machines. |
|
| Back to top |
|
|
Henry
science forum addict
Joined: 15 May 2005
Posts: 58
|
| Posted: Wed Sep 21, 2005 9:45 pm Post subject:
Re: Efficient generation of random permutations from random bit streams.
|
|
|
On Wed, 21 Sep 2005 15:50:19 -0400, "Christopher V. Kimball"
<kimball@ntplx.net> wrote:
| Quote: | Can a random permutation of N objects be constructed from log2( N!) +1
random bits?
The methods I'm aware of are inefficient relative to the log2(N!) limit.
|
If what you are asking is whether given a number from 1 to N! can you
produce a distinct permutation, then the answer is yes: see
<http://groups.google.co.uk/group/sci.stat.math/browse_frm/thread/5a73bf3e1201f3af/fbef1227781b0780>
(sorry if the link wraps) |
|
| Back to top |
|
|
Henry
science forum addict
Joined: 15 May 2005
Posts: 58
|
| Posted: Thu Sep 22, 2005 8:56 pm Post subject:
Re: Efficient generation of random permutations from random bit streams.
|
|
|
On Wed, 21 Sep 2005 19:11:12 -0400, "Christopher V. Kimball"
<kimball@ntplx.net> wrote:
| Quote: | Is a "factorial base" decomposition unique?
|
Yes. Starting from 0, the kth place value x is constrained to be in
0<=x<=k and to be worth x * k!
0*0! + 1*1! + 2*2! + 3*3! +...+ (n-1)*(n-1)! = n!-1 so this is unique.
| Quote: | Practically, such a decomposition would be difficult even for N=52 on
today's machines.
|
Why? 52! is only
80658175170943878571660636856403766975289505440883277824000000000000
or so my spreadsheet tells me, so I could easily with any number of
this order or indeed much higher. I could not deal with all of them,
but that is not the question you asked. |
|
| Back to top |
|
|
Herman Rubin
science forum Guru
Joined: 25 Mar 2005
Posts: 730
|
| Posted: Thu Sep 22, 2005 11:30 pm Post subject:
Re: Efficient generation of random permutations from random bit streams.
|
|
|
In article <9OiYe.9347$H24.7900@fe11.lga>,
Christopher V. Kimball <kimball@ntplx.net> wrote:
| Quote: | Can a random permutation of N objects be constructed from log2( N!) +1
random bits?
The methods I'm aware of are inefficient relative to the log2(N!) limit.
|
The best bound possible for all N is log_2(N!)+2. This is difficult
to attain; it requires computing N!, and from a random (0, N!-1)
number computing random numbers from 0 - N-1, 0 - N-2, etc.
The random numbers in these various ranges can be computed
in log_2(N!) + 2*log_2(N); this bound is pessimistic, and
the actual value for large N is likely to be somewhat more
than 1.6*log_2(N). This method involves only multiplication
by 2, addition, and subtraction, whereas the other involves
division and remainder.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558 |
|
| Back to top |
|
|
Christopher V. Kimball
science forum beginner
Joined: 21 Sep 2005
Posts: 4
|
| Posted: Fri Sep 23, 2005 12:50 am Post subject:
Re: Efficient generation of random permutations from random bit streams.
|
|
|
How do you get the N-1 random variables (0..N), (0...N-1),...(0..1) from
the(0...N!-1) number that has the ~1.6*log_2(N!) efficiency you describe? |
|
| Back to top |
|
|
Herman Rubin
science forum Guru
Joined: 25 Mar 2005
Posts: 730
|
| Posted: Fri Sep 23, 2005 1:26 pm Post subject:
Re: Efficient generation of random permutations from random bit streams.
|
|
|
In article <02KYe.3347$Xa.1657@fe12.lga>,
Christopher V. Kimball <kimball@ntplx.net> wrote:
| Quote: | How do you get the N-1 random variables (0..N), (0...N-1),...(0..1) from
the(0...N!-1) number that has the ~1.6*log_2(N!) efficiency you describe?
|
It starts with 0...N-1. Divide the number K by (N-1)!,
getting a quotient R and a remainder K'. Then R is
uniform 0...N-1 and K' is uniform 0...(N-1)!-1, and
they are independent. This has the efficiency
log_2(N!)+2. The problem with this method is that
N! may not fit, and the divisions may be difficult
to carry out. Multiple precision arithmetic is usually
quite slow.
The easy method to get a random number from 0 to K-1 with
the smallest expected number of bits is the following; it
can be speeded up by combining steps in which termination
is not possible.
I = 0; J = 1;
while (; {
while (J < K) {I = (I<<1) + RBIT; J = J <<1;
if (I < K) {return I; exit;}
I -= K; J -= K;}
The reason this works is that I is always uniform 0...J-1.
Using this from N down to 2 gets the efficiency
about log_2(N!) + 1.6*N, which still is asymptiotically
good. It can be improved with some effort.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558 |
|
| Back to top |
|
|
Christopher V. Kimball
science forum beginner
Joined: 21 Sep 2005
Posts: 4
|
| Posted: Mon Sep 26, 2005 2:24 pm Post subject:
Re: Efficient generation of random permutations from random bit streams.
|
|
|
|
Thanks! |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Probability
