Big-O Notation For Coding Interviews and Beyond/

...

/

Permutations

Permutations

This chapter shows how one can reason about recursive problems without extensive mathematical knowledge

We'll cover the following...

Finding permutations of a given character or integer array is a common interview problem. Assume we have the following character array of size 4 with no repeating characters, and we need to find out all the permutations of size 4 for the below array.

%0 node_1 a node_1539054963290 b node_1539054953233 c node_1539054981105 d
Character Array to Permute

The permutations will be generated using recursion and we'll give a solution that is easy to understand, even though it may not be the optimal one in terms of space usage. Our emphasis is on learning to reason about the complexity of algorithms. Take a minute to read through the code listing below before we attempt to figure out the time complexity.

Permutation Implementation

Press + to interact
class Demonstration {
    public static void main( String args[] ) {
        char[] array = new char[] { 'a', 'b', 'c', 'd' };
        char[] perm = new char[array.length];
        boolean[] used = new boolean[256];
        permute(array, perm, 0, used);
    }
  
    /**
     * Note that we are using a boolean array to remember what
     * character we have already used and another array perm 
     * which contains the actual permutation. We can actually
     * generate permutations without these additional arrays but
     * for now the desire is to make the code easier to understand.
     */  
    static void permute(char[] array, char[] perm, int i, boolean[] used) {
        
        // base case
        if (i == perm.length) {
            System.out.println(perm);
            return;
        }
        for (int j = 0; j < array.length; j++) {
            if (!used[array[j] - 'a']) {
                perm[i] = array[j];
                used[array[j] - 'a'] = true;
                permute(array, perm, i + 1, used);
                used[array[j] - 'a'] = false;
            }
        }
    }  
}

The number of permutations for a string of size n is n! ( pronounced as n factorial). A factorial of a number is the product of all the numbers starting from 1 up to n. Below are a few examples:

0! = 1
3! = 3 x 2 x 1 = 6
5! = 5 x 4 x 3 x 2 x 1 = 120
10! = 10 x 9 x 8 .... 1 = 3628800

The number of ways to permute a string of size n is n!. One way to rationalize is to think of n empty slots.

We can pick any of the n characters and put it in the first slot. Once the first slot if fixed, we can fill the second slot in any of the n-1 ways using the remaining n-1 characters of the string. In the same vein of reasoning, we can fill the third slot in n-2 ways, and so on and so forth. By the time we get to the nth slot, there will only be one element left and we will only have one way to fill it up. Thus the total number of ways we can fill up n empty slots (i.e. arrange n elements in a different order or by the number of permutations) is:

n∗(n−1)∗(n−2)...1n * (n-1) * (n-2) ... 1

= n!=\:n!

We can immediately see that the time complexity for generating all the permutations is also O(n!). Note that even though this is a recursive problem, it doesn't lend itself to the divide-and-conquer strategy; it can't be broken up into smaller subproblems that can then be combined. The solution is to find every possible permutation, and that would take n! time.

Having said that, the intent of this chapter is to reason about complexity using recursion trees, so let us draw out the recursion tree and see how one can deduce the complexity ...