in Books, Doing Books, How to Solve it by Computer

How to Solve it by Computer #13

Algorithm 8.4: Design an algorithm that generates all permutations of the first n integers taken r at a time and allowing unrestricted repetitions. This is sometimes referred to as sample generation. The values of n and r must be greater than zero.

This was also something I never did properly, writing combinatorial algorithms. I want to clean up and do it finally.

So the problem is that we want these permutations of integers. Given n = 4 and r = 2, we get:

These are n^r = 4^2 = 16 possible elements. For r = 2 the algorithm is pretty simple:

We iterate over every x and every y. We could write a macro which just creates more variables given r. But let’s take a more general view.

We can see that the sequence [1 2 3 4] is repeated over and over again. The only thing that changes is the first number. More generally, we combine our first number with all the sub-permutations, then our second number, etc.

Again, no super hard code. We basically iterate over our existing result set and append the integers up to n to each one and then do it again recursively. I’m surprised that it was that easy :D

And here’s some output:

Write a Comment