Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.


1. Introduction

In this tutorial, we’ll present the recursive and iterative algorithms for generating permutations with repetition. Finding all permutations with repetition is a combinatorial problem like generating all k-combinations of a set.

2. Permutations With Repetition

Permutations with repetition of a set \boldsymbol{A} are ordered tuples whose elements come from \boldsymbol{A} and may be repeated. If the tuples’ length is k, we call them k-tuples. For example, with A=\{1,2,3,4,5,6,7\} and k=4, the following are 4-tuples of A:

    \[\begin{aligned} (1,1,1,1) \\ (1,2,3,4) \\ (5,4,2,2) \end{aligned}\]

Our task is to generate all the k-tuples of a set A. If |A|=n, there are n^k such tuples.

Here, we’ll take A to be of the form \{1,2,\ldots, n\}. We don’t lose generality in doing so because we can map each set of n elements to \{1,2,\ldots,n\}. So, we can map each k-tuple of \{1,2,\ldots,n\} back to the elements of the original set.

To ease notation, we’ll write 1234 instead of (1,2,3,4).

3. Recursive Algorithm for Generating Permutations with Repetition

We can define permutations with repetition by induction over k:

  1. If k=0, then the only permutation is the empty one that we’ll denote as [\ ].
  2. If k > 0, then any k-tuple can be obtained by prepending a number from \{1,2,\ldots, n\} to a (k-1)-tuple.

These rules give us the logic to follow recursively. k = 0 is the base case, and for each k>0 we prepend every i \in \{1,2,\ldots,n\} to each tuple we got for k-1.

3.1. Pseudocode

Here’s the pseudocode of the recursive solution:

Rendered by QuickLaTeX.com

3.2. Example

Let’s see how the FIND function works.  Let’s say that n=5 and that we want to find all the 3-tuples. The call FIND(n, 2) returns 25 2-tuples:

    \[\begin{aligned} 11 && 12 && 13 && 14 && 15 \\ 21 && 22 && 23 && 24 && 25 \\ 31 && 32 && 33 && 34 && 35 \\ 41 && 42 && 43 && 44 && 45 \\ 51 && 52 && 53 && 54 && 55  \end{aligned}\]

To get 3-tuples, we first prepend 1 to all the 25 2-tuples and get:

    \[\begin{aligned} 111 && 112 && 113 && 114 && 115 \\ 121 && 122 && 123 && 124 && 125 \\ 131 && 132 && 133 && 134 && 135 \\ 141 && 142 && 143 && 144 && 145 \\ 151 && 152 && 153 && 154 && 155 \\ \end{aligned}\]

Then, we prepend 2:

    \[\begin{aligned} 211 && 212 && 213 && 214 && 215 \\ 221 && 222 && 223 && 224 && 225 \\ 231 && 232 && 233 && 234 && 235 \\ 241 && 242 && 243 && 244 && 245 \\ 251 && 252 && 253 && 254 && 255  \end{aligned}\]

Then, after doing the same with 3, 4, and 5, we get all the 125 3-tuples.

4. Iterative Algorithm for Generating Permutations with Repetition

The recursive algorithm makes the k-tuples available once it generates them all. That is, we can’t access any k-tuple before generating all of them first. Since there are n^k of them, the recursive algorithm’s space complexity is \boldsymbol{O(n^k)}.  If our application is memory-constrained, this isn’t the way to go.

Moreover, we usually want to filter the permutations to keep only some of them. So, at any time of execution, we’ll be processing a single k-tuple, which is why there’s no need for storing all the permutations. It would be best if we could do something like this:

  • ask for a permutation
  • process it and go to the previous step to ask for another k-tuple

In that case, we’d need only O(k) space, which is a significant reduction compared to the recursive algorithm whose memory complexity grows exponentially with k. We can achieve that with an algorithm that receives a permutation as its input and returns the next permutation in the lexicographic order. Let’s name that algorithm NEXT. Then, we start with the first permutation, and then, by calling NEXT, we  iteratively generate and process all the other permutations:

Rendered by QuickLaTeX.com

So, NEXT should return the next permutation if there is one, and failure if we ask it for the last k-tuple’s successor. But, how do we implement NEXT?

4.1. Generating the Next Permutation

This is the main idea. A permutation x=x_1x_2\ldot sx_k and its successor x'=x_1'x_2'\ldots x_k' will have a common prefix. For example, with n=7, 12735 is the successor of 12734, and their common prefix is 1273. The suffix that is different starts at the rightmost \boldsymbol{x_j} lower than \boldsymbol{n}. In this example, that was 4 in 12734. We increment it by one and get 1235.

However, this doesn’t cover all the cases. What if there’s an n in the suffix we’re about to change? Let’s consider 12737. The rightmost element lower than n=7 is 3. But, if we increment by 1, we get 12748, whereas the actual successor is 12741. So, what’s the correct logic?

The solution is to realize that the operation we should perform on every \boldsymbol{x_{\ell}} after \boldsymbol{x_j} is the circular increment. We increase by one all the numbers except n, which we change to 1. But, if all the numbers are equal to n, then there’s no successor. It’s the last permutation, so we should return failure to stop the caller’s loop.

4.2. Pseudocode

Here’s the pseudocode of NEXT:

Rendered by QuickLaTeX.com

As we see, apart from the auxiliary variables, \boldsymbol{NEXT} doesn’t require more than \boldsymbol{O(k)} memory to find the input’s successor.

4.3. Example

Let’s work out an example. Let’s say that n=7 and x=x_1x_2\ldots x_5=12777.

First, we determine where the suffix to change starts. The rightmost element lower than 7 is 2, so the suffix to change is 2777. Next, we increment 2 by 1 to get 3 and replace all sevens with ones. The permutation we get is 13111, which is the correct result.

It’s interesting to note that if we used \boldsymbol{\{0,1,\ldots, n-1\}} as \boldsymbol{A} instead of \boldsymbol{\{1,2,\ldots, n\}}, \boldsymbol{NEXT} would amount to incrementing by 1 modulo \boldsymbol{n}.

5. Conclusion

In this article, we presented two ways to generate all the permutations with repetition of the set \{1,2, \ldots, n\}. The recursive algorithm returns all the permutations at once, whereas the iterative method processes them one by one and has a lower space complexity.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!