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.

Sudoku Checker

Sudoku Checker

Problem Statement

Given  a vector<vector<int>> of size 9*9. Check whether it is a valid Sudoku or not.  

Problem Solving 

• I thought of starting with Iterators, writing Iterators for row iterator a column iterator and square iterator. 
• This got me involved in a lot of Object Oriented Problem and how to implement == nicely. 
• That got me stuck on the double dispatch problem and further after few frustrated days, I found a book, Effective C++. 
• Now after having read that book and coming to chapter 2. I thought I had one solution and I restructured the Object modeling and yes it did work.
• This whole thing took a lot of time. around 2 weeks now. 
• Then I peeked in the book and answer in the book seemed very short and concise.
• Hah.. I think I created a complex solution to a simpler problem. 
• The solution in the book is very clean, basically instead of iterators and their complex hierarchy and initialization on objects this solution has a function that takes in a row_start , row_end, col_start, col_end and the original matrix. 
• Instantly I can see how easy it would be, the signature of the function would reveal it's algorithm. 
• But okay. I think this was a good learning. 
• The solution would be iterate all rows cols and sub matrices and check if anyone has duplicates. 
• checking for duplicates can be done via a set or bit vector. 

 Learning

• Multiple learning here. 
• First I think I should fork my problem solving skill from OO modelling skills. 
• So I have picked up a new book Programming Pearls. 
• All other learning were related to c++ and it's OO nature. 
• This took a lot of time and broke the rhythm. 
• I still do not know when is the time to give up and look in the book. 

Online Sampling

Online Sampling

Problem Statement

Write a program that takes a stream and reads value from it to maintain a random subset of k elements. 

Problem Solving 

• Instantly I think about a function that takes in a stream
• First fetches k values to fill a vector of size k. 
• On further input decides whether to take this element or not based on psuedo random number. 
• Then randomly select an index in the vector and write over that value the new value. 
• But I am not sure, If I understand the question correctly. 
• I'll probably code it and run it on the EPI judge and then get back here.  
• Well this does not work. 
• After understanding the solution which is quite similar with a stark difference which solves the issue. 
• The random number generator is used to generate numbers from 0 - all number seen till now. If that number lies in 0 - k range then we replace that index with the new number. 
• However here all subset generated in sequence only differ by 1 element. 

Learning

• I have clearly to do a deep dive in probability as I had trouble understanding what makes a subset really random. 
• The offline sampling problem gave a lot of clarity however this is new. 
• Also the new random num generation lib constructs in c++ 11 needs to be defunct. 
• Huh.. few tasks here. okay it's just okay to admit that there are few things I do not know and that as this progresses, so will I. 
• Keep on...

Offline Sampling

Offline sampling 

Problem Statement 

Write a program that taken a vector on n integers and return a random sample of size k. All sample must be equally likely. 

Problem Solving

• At first, I had trouble understanding what exactly is a sample,how do measure a probability of such a permutation. 
• After a while I thought that may be generating randomness could be used by a lib function like rand()
• We could use rand() k times to generate a number between 0-n and then selecting it. we will loop this until we have found unique k indexes. 
• This works however this does not sound about right. 
• To do this we also would require a set to store what indexes have been selected and whether a selected index is already used or not. 
• The only problem with this is the extra over head of first storing and searching in a set. 
• We could further remove this by moving the selected element to the end of the array and then using rand() only from 1 - (n-1) . This does it in linear time without the use of any extra memory. 
• Find Code here.

 

Learning

• This problem was hard to think and easier to understand and implement. 
• The key hint is that if you have k elements found how do you select the k + 1 element. 
• This problem is a really useful one as I had never solved this problem before. 
• Also this problem was once asked in some interview, the question was how to shuffle a deck of cards. 
• So yeah this is one key concept I have learned using this problem.

Next Permutation

Next Permutation

Problem Statement

Given a permutation M, return the next permutation.

Problem Solving 

•  In this problem, the first thing that clicks is to observe examples. 
• And after multiple attempts, I started seeing a pattern. 
• First of all we need to see if there is a next permutation. If the sequence is already in the descending order then there is no need to work on it. 
• So starting from the last element we need to find the first element in reverse order which is out of order. 
• Post that since we need the next permutation and the next permutation should only involve the element at the least place value. That means that we have to work with the element just next to the element that is found earlier. 
• Now we need to find an element in the range to swap it with. This came after a long time that the max element smaller than the eligible element should be swapped. 
• Here we can optimize since to find such a element in an already sorted array is a eay task. 
• Post swapping the new range should be sorted. But recalling that this sequence is already sorted we can just reverse it instead of sorting it. 
• The solution works but it took lot of time to figure out. 
• Find code here. 

Learning

• Doing examples is also frustrating emotionally until you let go of fear that you can do this. Doing these problems is raising confidence every day. I feel proud and confident. 
• Simple edge cases and off by error are really the take away. 
• Also reverse iterator to forward iterator = reviterator.base(0 but this is risky as it has a convoluted meaning.  
• I need to understand upper bound and lower bound as well as these are also confusing sometimes. 
• Overall the problem was solved and this time I paid attention to code writting it as consice as possible. 
• Also this time I first wrote it on paper and then on pc. 
• Altogether good, I am feeling the benefits of writing and pursuing this exercise.