Programming Languages (CS302 2007S)

P. Bratley - Permutation with Repetitions

These notes are also available in PDF.

Comments on:

Bratley, P. (1967). Algorithm 306: Permutation with Repetitions [G6]. Communications of the ACM 10(7), July 1967, pp. 450-451.

Is the ordering of the labels (1-12) in that order for a reason?

Even though there were a few lines of code, it took me a while to read through the algorithm. The fact that L1 to L12 do not appear in ascending order made it a little bit harder for me to read. Is there any special reason why the L's are not organized in ascending order?

Why not in order?

You know, I expect that it's a design decision, but I'm not sure particularly why he made that design decision.

Is "own integer" somewhat equivalent to a static integer variable?

Yes. It's a variable that is local to the procedure, but that persists across multiple calls.

This algorithm is unbelievably confusing to interpret. Do you think it was just as confusing to write as it is to read?

No, I think the author had a clear sense as to how the algorithm would work, and expressed it that way. Of course, getting it perfectly right was clearly hard, which we know because it had to be rewritten and because it still does not meet its stated goal of putting the results in order.

What do the numbers after the L mean,e.g L12?

Those numbers are parts of the labels.

When they programed this, did they naturally come up with those many gotos? If not, why would they choose to use this many in the paper?

I think you've answered your own question - It's unlikely that someone would insert this many goto statements and labels unless it was the way they regularly programmined.

Algorithm 306 definitely showcases how complicated an algorithm can be with goto statements. It is quite difficult to decipher how the data flows through the algorithm. Aside from the trouble I had finding out what exactly this algorithm tries to accomplish (due to what I consider poor documentation), it is unclear to me how these go to statements work. For example, if I go to L12 and it's an assignment satement, should I just move to the next line? Is the command after a goto ever read? For example, in line 9 of the algorithm, one can go to L99 and then "end". Isn't that last "end" superflous since it might not be read and L99 leads to the end of the algorithm anyway?

A goto statement simply transfers control to the given label. Any code after the label is executed. The end statement is necessary, because you have to mark the end of an algorithm. (Remember, the algorithm would appear with other code, so the end of one and the start of the next must be distinguished.)

I understand what the algorithm does and returns by means of trying different inputs, but in general thought it was very complicated and confusing. For example, L6 could very easily have been implemented with a for loop, similarly L4, L5. Why did the writer of this code, want to use so many gotos, could it not be implemented any other way then (1967)?

I do not know about the author's design decisions. However, if you look at the code more closely, you'll see that things that look like loops are a bit more subtle. For example, the L6 loop returns to the top in two different places places.

A shining example of Dijkstra's point in the previous article. After implementing this algorithm in C, I didn't know how it worked. After reimplementing it without the use of GOTO, I still didn't understand it. Only after I sat down and analyzed it with the intent of not looking like an idiot on monday did I finally grasp what it is trying to do. While the pseudocode is concise, the use of GOTO statements obfuscates the underlying algorithm to the point where it is barely above gibberish.

You may be the only one in the class who now knows what the algorithm does.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Sun Apr 29 11:27:01 2007.
The source to the document was last modified on Sun Feb 4 20:48:04 2007.
This document may be found at

You may wish to validate this document's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky,