Compute Random Permutation

Compute Random Permutation

Problem Statement 

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. 

Problem Solving

• 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.  

Learning

• 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.