.jpg "Generating permutations with Heap’s algorithm")
This evening I wanted to solve a particular problem, and it required me – or so I thought – to permute an array of items. Back in the day I wrote an article for PCPlus on the subject and mentioned in there Heap’s algorithm. I hasten to add here that “Heap” here is not the traditional computer science heap, or even the application memory heap, but B.R. Heap, who first formulated and published this algorithm in 1963 (pdf).
Permutation 1: we're out
Wikipedia has a small article on Heap’s algorithm (although Heap’s paper is not that difficult to read – it even has flow charts!), and even gives some pseudo-code for it:
procedure generate(n : integer, A : array of any): if n = 1 then output(A) else for i := 1; i ≤ n; i += 1 do generate(n - 1, A) if n is odd then j ← 1 else j ← i swap(A[j], A[n])
The problem with this pseudo-code is that, although it looks simple enough, there is no discussion as to whether the array A is zero-based or one-based. Some perusal will lead you to assume that it is, in fact, one-based (that is, the first element is at position 1, and if there are n elements, the last element is at position n). Fair enough, but of course, I’m sure that most of my readers are firmly in the zero-based camp in real life, as am I. How do you change it to cater for those types of arrays? There are a couple of answers, I suppose.
The first one is to keep the pseudo-code pretty much as is. Notice though that the only time the elements of the array are referenced is in the call to the swap function, so the simplest answer is to rewrite that to something like this:
procedure swap(x, y : integer, A : array of any): temp = A[x - 1] A[x - 1] = A[y - 1] A[y - 1] = temp
and then you just call it with the two indexes j and n and the array, and let the routine do its stuff taking care of the array being zero-based.
Permutation 2: we're asleep
Of course, the second one is to rewrite it completely to assume zero-based arrays. Here’s a JavaScript example where I chuck away the variable n and call it what it really is: the index of the last item you are permuting up to:
var generatePermutations = function (items, process) {
"use strict";
var generate = function (last, items, process) {
var
i,
swap = function (x, y) {
var temp = items[x];
items[x] = items[y];
items[y] = temp;
};
if (last === 0) {
process(items);
}
else {
if ((last & 1) !== 1) {
for (i = 0; i <= last; i += 1) {
generate(last - 1, items, process);
swap(0, last);
}
}
else {
for (i = 0; i <= last; i += 1) {
generate(last - 1, items, process);
swap(i, last);
}
}
}
};
generate(items.length - 1, items, process);
};
generatePermutations(['a', 'b', 'c', 'd'], function (items) {
console.log(items.join(""));
});
Notice that I wrapped Heap’s algorithm in a function that you actually call, so you don’t have to remember that you don’t pass in the number of items, just the index of the last item.
UPDATE (9-Jul-2015):
I’ve been having a chat with the author of the Wikipedia piece – it seems the pseudo-code I’d copied and inserted above is not correct. Be warned! There’s been a couple of changes to that pseudo-code in the interim on their page, so I recommend nipping over to Wikipedia to review the latest, rather than me copying it here.
Anyway, in going back over my notes for that, I discovered that my JavaScript code was doing one too many swaps per call of the inner function. (In essence, I threw in some calls to console.log() to analyze the recursion – yay for sophisticated debugging!.) So I made a small change to the routine. Here’s the new one:
var generatePermutations = function (items, process) {
"use strict";
var generate = function (last, items, process) {
var
i,
swap = function (x, y) {
//console.log(x + " <=> " + y);
var temp = items[x];
items[x] = items[y];
items[y] = temp;
};
//console.log(last);
if (last === 0) {
process(items);
}
else {
// if last is even
if ((last & 1) !== 1) {
for (i = 0; i < last; i += 1) {
generate(last - 1, items, process);
swap(0, last);
}
}
// else last is odd
else {
for (i = 0; i < last; i += 1) {
generate(last - 1, items, process);
swap(i, last);
}
}
generate(last - 1, items, process);
}
};
generate(items.length - 1, items, process);
};
generatePermutations(['a', 'b', 'c', 'd'], function (items) {
console.log(items.join(""));
});
Notice I left in the state-of-the-art debugging statements (albeit commented out) just for you. You’re welcome.
Now playing:
Spandau Ballet - Round and Round
(from The Singles Collection)
Loading links to posts on similar topics...
4 Responses
#1 bluss said...
08-Jul-15 9:58 AMHi, the wikipedia article had an error in its pseudocode. As you can see in the text, the algorithm should use exactly one swap between each permutation. I've updated the article and illustration to correct this, but by now the error is all over the internet! Hope this helps and let's enjoy how much more beautiful the algorithm is without extra swaps.
#2 bluss said...
08-Jul-15 10:00 AMOh, I see your javascript version already corrects this. Excellent!
#3 julian m bucknall said...
08-Jul-15 10:37 AM@bluss: Thanks for taking the time to read my post! Although I quoted the Wikipedia article and the pseudo-code there, I think I actually based my JavaScript code more on Heap's discussion in his paper instead. So, maybe that's why I managed to correct the original issue :)
Cheers, Julian
#4 Akinwale Habib said...
06-Aug-17 3:47 PMGreat write up. I find your article easy to understand and detailed.
Leave a response
Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.
_emphasis_**strong**[text](url)`IEnumerable`* an item1. an item> Now is the time...Preview of response