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.

Apply Permutation

Apply Permutation

Problem Statement

Write a program that takes a permutation array and a input array and reorder the input array as per the given permutation.

Problem Solving 

• I can see that this seems to be a linear time problem. 
• We need to apply permutation inc cycle.
• Start at 0 replace current position at 0 with previous input, swap previous input at current position. continue till end. 
• However there are multiple missing things in this solution. 
• As there can be multiple cycle in the same array. Therefore we need mechanism to break from cycle and then run on the next cycle. 
• To break the cycle we need to keep an bool index whether the position is processed or not. 
• and to go to next cycle we can always scan the processed array for non processed items and then start the process there. 
• This seems okay. 
• Find code here.  

Learning

• This question might seem simple but to implement it correctly is difficult. 
• Since I coded through the problem solving my code also looked tangled and complex. 
• After multiple debugging sessions and fixing problems. The code looked in a very bad shape. 
• However it passed all test cases. 
• Then I looked at the answer to find it to my surprise, that the code written is so much more elegant than what I had written. 
• However there is space optimization in the book's answer but ignoring that also the code was  much more simple. 
• Later I refactored my code into that shape. Felt both good and bad. 
• Writing good code is really really difficult. I understand it now. Everyone can code but to make proper sentences in the language is the art. To write pieces that are elegant and clear and concise. 
• Now that I have refactored it. It look good.
• Also one key insight is that whenever you feel like using an iterator that runs through all the elements in linear fashion use a for loop. and when needed to skip use continue or empty loop cycle. No need to write make complex iterator advances. 
• Small question lots of learning. 

Enumerate All Primes to N

Enumerate All Primes to N

Problem Statement

Write a program that takes an integer argument and returns all primes between 1 and that integer. 

Problem Solving

• There is not much of any solving here as I already know an ancient and well known algorithm for this. It's called the Sieve of Eratosthenes. 
• The idea is to create a list of all numbers to n. 
• Then iterate all number from two and at each number keep marking the multiples of those numbers as false or -1. 
• The iterate to the next non -1 number and do the same. 
• Find Code here. 

Learning

• Must always check for bounds. 
• The time complexity is n2 and space in O(n). 
• There is a way to save some space as the even numbers can be removed. 
• std::iota in the numeric header is a library function that can fill array with increasing numbers.
• There is also a Segmented Sieve which is used for large ranges and by segmenting them into smaller chunks
•  Since I could not understand all aspect of optimizations to this problem I am currently leaving behind this problem and moving on to next one.