Heap’s Algorithm

Any sophomore computer science student knows that there are $O(n!)$ permutations of any given array. But do you know how to produce those permutations? I didn’t , so I Googled it.

One simple strategy is to pick an element, then pick from those remaining, and so on until a single permutation is achieved. Then just backtrack one step and change your selection, finish the permutation again, and so on. For example, if you want to permute ABCD :

1. Select A
2. Select B, yielding AB
3. Select C, then D, yielding ABCD, your first permutation
4. Back up two positions and select D, then C, yielding ABDC
5. Back up three positions and select C, then B, then D, yeilding ACBD
6. And so on…

This might be a pretty straightforward implementation using recursion and a running collection of element lists (several copies). This is memory and CPU intensive, so an in-place solution would be nice.

Heap’s algorithm provides an in-place swapping method to find each permutation in about one step each, so it is very efficient. It is named after B. R. Heap, not after your favorite semi-sorted tree.

The core idea is very intuitive: Hold the last element of your list while recursively permuting the other n-1 elements (one must understand recursion). Then swap that last element with one of the others, and permute n-1 elements again. This way you get every possible permutation of n-1 elements for every possible fixed element value at position n. This should get us all permutations.

The tricky part is swapping out the nth element for one of the others. You might be tempted to write a loop that picks a new element from the n-1 to swap with, but remember that we permute the n-1 elements at every step, effectively scrambling them. Take `AB C `as an example. The n-1 permute leaves us at `BA C.` Say we swap `C `with `B`, giving us `CA B`. The n-1 permute then takes us to `AC B`. We know that we should swap `B `with `A`, because that is the only choice left to sit at the fixed position. And it is at position 0, just like the previous swaps!

The six permutations produced look like this :

`ABC -> BAC -> CAB -> ACB -> BCA -> CBA`

Let’s apply the same swap-with-zero strategy to four elements, abbreviating the three-element permutations for clarity :

`ABCD -..-> CBAD -> DBAC -..-> ABDC -> CBDA -..> DBCA -> ABCD --X..OOOPS`

We started repeating permutations before finding all of them. It turns out that `AB `is a different kind of permutation than `ABC `because of the length.

To see why, start by assuming that our permutation method will, if run twice, return the same permutation it started with. (This can be proven through induction once we understand the whole algorithm, but I will leave out the proof.) When `ABC `is being permuted, the first two elements are permuted three times while the elements take turns at the right position. This odd number of permutations makes the first two elements unstable in the sense that, every time we swap in the nth element, they are in a different order.

But when `ABCD `is being permuted, the `ABC `scramble is being performed an even number of times (four times), so it is stable except for the swap of the nth element. It is easier to see if we look at the algorithm output right before it swaps the nth element:

`BA -> AC -> CB `

`CBA -> CBD -> CAD -> BAD `

`BADC -> AECB -> EDBA -> DCAE -> CBED `

`CBEDA -> CBEDF -> CAEDF -> BAEDF -> BAECF -> BADCF`

Notice that the odd-length scrambles are stable except for the one-character substitution, while the even-length ones are not. This is a hand-waving explanation at best, but it works to give us an intuitive understanding of the algorithm.

So, for even-length permutations, the n-1 swap is always done with the first element, while for odd-length permutations, the n-1 swap is done with the kth element, where k is a counter from position 0 to n-2 that increments every time we do this.

The recursion is still there, but with very little extra state, very few loops and conditionals. And it takes barely more than $O(n!)$ swaps, which is close to ideal. You can find the code in all its glory on Github, but here it is for your edification. Uncomment the console.log’s to see each operation in action.

```var margin = ''

function permute(list, action) {
function swap(n,m) {
margin += '   '
//console.log(margin + 'swap ' + n + ' ' + m + (m==n ? ' (NOP)' : ''))
tmp = list[n]
list[n] = list[m]
list[m] = tmp
margin = margin.replace(/   \$/,'')
}

function generate(n) {
margin += '   '
//console.log(margin + 'generate ' + n)
if (n==1) action(list)
else {
for (var i=0; i<n; i++) {
generate(n-1)
//console.log(margin + 'i = ' + i)
swap(n%2 ? 0 : i, n-1)
}
}
margin = margin.replace(/   \$/,'')
}
generate(list.length)
}

permute(['A','B','C','D','E'], function(list){console.log(list)})
```

Deep or Wide (Job Interview Preparation)

I had the pleasure of a going through a couple of job interviews in the past month. I was pleased with my performance on both. They were pleased with my performance on at least one.

Both companies are cool tech firms, but the interviews were very different.

Wide Company

Wide Company wanted to know if I was a real, modern software developer. This means that they wanted to know about my knowledge of tools and techniques, and my understanding of the principles of modern software architecture. They belted out a series of short-answer questions that sounded something like this:

• What is a design pattern? (A well-structured solution to a common software problem. Most of the time means creating an interface where you weren’t planning to use one.)
• Can you name a design pattern? (Sure – me laughing – Singleton)
• OK, what’s a Singleton? (OK, here is where I expressed regret at not naming Decorator or Composite, since those are more interesting. But a Singleton is a pattern – or antipattern if you don’t like it – that only allows one instance through a factory method. It accurately models resources such as the operating system in some instances.)
• How familiar are you with JavaScript? (Pretty good. I know what variable hoisting is.)
• How familiar are you with Java? (Pretty darned good. I can solve problems using Java in job interviews.)
• Have you ever used git? (I deploy my web sites using git and use it extensively at work, independent of our official VCS.)
• Do you know about AngularJS? (Well, I know it is an app framework, something resembling MVC. I don’t really know it right now.)
• Have you ever deployed anything to the cloud? (Well, not really.)
• What is a Lambda expression? (Roughly an anonymous function that may or may not capture some lexical scope. If it does capture variable values in this way, it can be called a closure.)
• What is dependency injection? (Also called inversion of dependency, it’s when you decouple a class from a class it uses by having the latter conform to an interface and having the object specified at run time rather than instantiating it directly. The Spring framework automates this pattern.)

There were more, but I have forgotten them. Or perhaps blocked out the painful memories…

Deep Company

Deep Company wanted to know how I solve problems using algorithms, data structures, and software.

They sent me a shared document and asked me to type solutions that they reviewed live during the interview. They gave me programming problems, and I chose to solve the problems in Java. In this interview, the questions resembled exam problems from a university course, and they asked me not to reveal any questions outside of the interview. So I won’t! Instead, I’ll make up problems of similar difficulty :

• Suppose you have two circular linked lists. Write a method that tells me if the two lists are equal. The signature might look like this :

boolean areEqual (Node a, Node b)

Now this is the point where you are supposed to ask questions, which I did. But I tried to provide my own answers where I could.

1. Can I assume Node has fields Node.next, and Node.value?
2. Are the passed nodes “head”, “tail”, or neither? A: Neither. There is no head or tail, and elements do not have a position index. It does not follow the traditional list API.
3. Are the lists considered equal if the contain the same values in any orientation, regardless of whether a and b point to the same location in those lists?
4. Can the nodes be null? Are there any one-element lists?
5. And so on…

If you take the restriction that the nodes passed are supposed to be equal, and every element value matches at every position going around the list, then this problem can be solved by iterating around the list and checking each value for a match, and stopping when you reach the first node again. I wrote my answer mostly ignoring null edge cases at first,

• Now write the same method, but without the assumption that the passed node positions have to match. Now a and b represent any arbitrary node in the circular list, but I want equals to be true if either list matches the other where you are allowed to start at any position.

Here I actually wrote down sample data structure instances as an example, and asked if they would be considered equal or not.

```            a        b
|        |
v        v
Apple -> Banana -> Cherry ---
^                         |
|--------------------------
```

I hope that you understand my ASCII art. I may need to work on my posting skills. Please comment if you have a cool tool for drawing data structures in WordPress or HTML.

And, yes, those two structures are supposed to return true for equality.

Now the problem becomes harder, but is still doable. You can brute-force the solution with a two-level loop, one rotate the starting position until the starting elements match in value, another to check each position for equality after that.

• Can you optimize your solution?

Optimization depends on the use cases. An optimization for one case makes other cases run slower.

Suppose the lists contain lots of repeat values. If that is true, then keeping a count of the number of occurrences of each value in a hash table would allow you to short-circuit the method and return false right away if the lists do not contain the same content counts. But if the counts match, you must continue and check their structure to make sure that matches as well.

So, to the future : I am preparing for more interviews. But which way? Deep or wide?

Do I write some sample codes in Spring, AngularJS, and EJB 3.0?

Or do I solve algorithm puzzles and then optimize them?

I’ll do a little of both.

Wish me luck!