Algorithms

Gray binary code is a way of expressing binary numbers such that consecutive numbers differ in exactly 1 digit. For example, in our conventional binary system, the numbers are 000 001 010 011 100 101 110 111 and so on In Gray, they are: 000 001 011 010 110 111 101 100 and so on In first system, when we go from ‘001’ to ‘010’, there are 2 changes namely the unit’s place becomes ‘0’ from ‘1’ and the next digit becomes ‘1’ from ‘0’. But in Gray’s system, ‘001’ becomes ‘011’ where there is only 1 change (that of 2nd digit). Gray codes are used in error correction in communication. Generating Gray codes of length n Is there a property we can use for easily generating the Gray codes of a given length? Yes! In our previous example, we generated all the Gray codes for n=3. Ignoring the most significant bit (MSB), notice how the 4th and 5th numbers are equal in their first 2 digits, as are the 3rd and 6th, 2nd and 7th and 1st and 8th. The last 4 numbers are reflection of the first 4 if we ignore the last digit. But the last digit is 0 for the 1st 4 numbers and 1 for the last 4… We have a recursive formulation. ...

I have started the 100 days of code challenge. I intend to use this time to check out new languages and frameworks and solve some fun problems. I will update this post with my logs. Aug 13 2018 D0 : Algorithms for calculating number of combinations and generating them in a lexicographical increasing order. Blog Aug 14 2018 D1 : Working on algorithm for generating all permutations. First I managed to generate all possible r repetitions of n i.e n^r. Next, I read up and wrote code on Heap’s algorithm. I am still not sure of the intuition behind the algorithm. Also, it does not generate the permutations in lexicographical increasing order. Aug 15 2018 D2 : Learned and implemented an algorithm that generates all permutations in a lexicographical order. It is not as efficient as Heap’s algorithm. Aug 16 2018 D3 : Stumbled across the game of Set. Wrote a small python script which generates all solutions of any given game. Aug 17 2018 D4 : Learning to use Puppeteer.js along with Google Cloud Functions. This dev.to post was very useful in getting me started. ...

In how many different ways can we select r objects from a collection of n objects? In mathematics, this is called combinations. The formula for the number of combinations is: where, n! denotes the factorial of a number that is the product of all numbers from 1 to n (inclusive). Prelude : A function for calculating factorial of a number public static long factorial(int n) { long res = 1L; for (int i = 1; i <= n; i++) { res *= i; } return res; } Calculating Combinations That was simple! Let us now move on to calculating the number of combinations given n and r public static long combinations(int n, int r) { if (r < 0) { return 0; } long res = 1L; if (r > n - r) { r = n - r; } for (int i = 0; i < r; i++) { res *= (n - i); res /= (i + 1); } return res; } What does this algorithm do? Recall that we need to find n!/r!(n-r)! which will be of the form n(n-1)...(n-r+1)/1.2...r. Similar to factorial, we initialize the result as 1 and multiply by n-i and divide by i+1. Will this result in a fractional number? No. This is because first, we multiply by n and divide by 1. Next, we multiply by n-1 and divide by 2. Now, either n or n-1 have to be even (as they are consecutive numbers). Similarly, next when we divide by 3, one of n,n-1 and n-2 must be divisible by 3. ...