Compute Random Permutation
Design an Algorithm that creates a uniform permutation from (0 – n-1). Given a random number generator that return a number (0 – n-1 ) with equal probability.
Use as few call to it as possible.
- Immediately I thought about the shuffle algorithm. However here we are provided with a number generator and have to create an array of unique elements.
- If I try to put random numbers in iterative way then there will be duplication issues so we can try to avoid them by checking if they are already present using a set and regenerating again if already present this could be very expensive in practice.
- So basically we somehow anyways need to check for duplicates as we will never know if the random generator has given us a duplicate.
- But there is no way of controlling the generator to give a number in a smaller range.
- I then tried filling up the array and shuffling it. however then again the init permutation will never be a result therefor not equally likely.
- No wait that can work actually, if the random number generator and the last place to swap are inclusive.
- It’s working fine. Find code here.
- I got lost in thought in this problem, may be due to self doubt. Since I originally thought of the shuffle approach but then from there I was getting lost.
- I think this is because I left randomness in between and then am very hesitant to approach these problems.
- Also this is a very nice code I have written very concise and clear code, feels good.
- I should complete the things I have started. Not leave things in between.