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.
    Leave a Reply

    Leave a Reply

    Your email address will not be published.

    This site uses Akismet to reduce spam. Learn how your comment data is processed.

    Catch Me On Social !!