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.

PCPlus logo 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.)

Album cover for Hello Waveforms Now playing:
Orbit, William - Surfin
(from Hello Waveforms)

Loading similar posts...   Loading links to posts on similar topics...

No Responses

Feel free to add a comment...

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

  •  Emphasize with italics: surround word with underscores _emphasis_
  •  Emphasize strongly: surround word with double-asterisks **strong**
  •  Link: surround text with square brackets, url with parentheses [text](url)
  •  Inline code: surround text with backticks `IEnumerable`
  •  Unordered list: start each line with an asterisk, space * an item
  •  Ordered list: start each line with a digit, period, space 1. an item
  •  Insert code block: start each line with four spaces
  •  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...
Preview of response