PCPlus 263: Generating simple permutations

I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the back of every issue. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. After all, the PDFs do appear on each issue's DVD after a couple of months.

This article was a fascinating one and as chance would have it — since it talks about "ringing the changes" — it appeared in the Christmas 2007 issue. Very festive, indeed. It was my eighth article for PCPlus and I was well into my stride structure-wise by now. Indeed this one has minimal changes from when I sent it up.

The subject is generating permutations or anagrams. The rationale for the article came from the anecdote I wrote about in the first few paragraphs (it was back in my early TurboPower days, if you want to know, say 15 years ago) and also from a presentation I'd found written by one of my favorite algorithm authors, Robert Sedgewick (and I lifted the couple of figures the article had from that presentation, although I did redesign them). Generating permutations seems like a simple algorithm, but it turns out to be hard to do it efficiently.

Not much else to say, really. I'll admit I haven't yet written an implementation of either the Johnson-Trotter Algorithm nor Heap's Algorithm. Perhaps I'll do it in another blog post.

(By the way, you try and find information about Heap's Algorithm without running into a lot of hits for the heap algorithm. Really, computer science researchers must change their name to something obscure before they invent and publish a new algorithm. Makes 21st century Google life a lot easier.)

This article first appeared in issue 263, Christmas 2007.

You can download the PDF here.

(Note to followers of this series. From this point on, I will publish these articles a year after they originally appeared. So the next one for January 2008 will appear at the end of this month.)

  Loading links to posts on similar topics...