Problem 6.17 compute random permutation - not satisfied with the solution


#1

This problem states that we are given a random number generator which generates uniform distribution of 0,…,n-1.

I was thinking about this for quite a long time and decided to look at the solution. It seems that the solution refers to problem 6.16. However, in solution for 6.16, the random generator is used in a loop to generate numbers between i and n-1 for i = 0 through k -1.

But I thought this is not allowed from the way problem 6.17 is stated. It states we are given only random generator to generate uniform numbers 0 to n-1 and that’s the only generator we can use.

With only this generator given, how do we generate uniform numbers is a smaller range (like from i though n-1)? Of course if we are able to generate in these smaller ranges, the solution becomes fairly simple. But how we generate within these smaller ranges? Note that using (our generator mod k) is not satisfactory since the distribution will not be uniform then.

So my question is, is there solution that solves the problem as stated, with only one uniform random generator in range 0,…,n-1?

I have the 1st edition of the book, I’m wondering if later editions have correct solution. Please don’t tell me the actual solution if it exists, i still want to try to solve it on my own, i just wanted to know if correct solution exists and how many calls (asymptotically) it makes to the random number generator.

Thanks,
Yev


#2

Hi @yevvi,

Sorry I cannot recall what the context in the first edition you have, so I cannot answer what your concern is but I think you shall try to find the solution in the second edition. I find the same problem in the second edition but everything looks ok to me.


#3

So you mean that it is possible to solve the problem with just one random generator that generates uniform probability numbers from 0 to n-1, where n is the size of the permutation, without having access to any other random distributions?


#4

@yevvi I have the same question as you. Were you able to solve the problem using such a random number generator?