Algorithm For Recursive Function For Permutations With Replacement In Python

So using the itertools module I'm able to code up a really slick bit of code for producing all permutations with replacement, but what I wanted to do was something using recursion.

Solution 1:

I think that the problem with your approach is that you had not committed, mentally to the recursion. Warning signs are having to create the whole sized array before you start, and finding that you need to know how big the whole thing is inside the body of routine recursive routine.

I came up with the following by thinking:

1) What will the answer of p_w_r be for k=1 and any n? I experimented on paper with n=2

2) Given that thing I think is the answer to 1, how do I make the answer for k=2 starting from the output of k=1.

I had to mess around a bit conceptually before I realised that the answer for k=1 has to be a list of single element lists itself (obvious when you see it, of course). From there, I could see that I needed to "stick this list" onto each element in the k+1 case.

       def permutations_with_replacement(k,n):
         # special case (not part of recursion)
         if k == 0:
            return []

         if k == 1
            return [[i] for i in range(n)]
         else:
            # Make the list by sticking the k-1 permutations onto each number 
            # we can select here at level k    
            result = []
            # Only call the k-1 case once, though we need it's output n times.
            k_take_one_permutations = permutations_with_replacement(k-1,n)  

            for i in range(n):
                for permutation in k_take_one_permutations:
                    result.append([i]+permutation)   
            return result

         print permutations_with_replacement(3,2)



momerath:~ mgregory$ python foo.py
[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
momerath:~ mgregory$ 

Solution 2:

I guess this doesn't help if you want to roll your own solution, but there's a very clean way to do this using itertools.product, which basically is equivalent to a Cartesian product.

import itertools

def permutations_with_replacement(n, k):
    # if you're on Python 2.x, use xrange(n) instead of range(n)
    return itertools.product(range(n), repeat=k)

n, k = 3, 3
for permutation in permutations_with_replacement(n, k):
    print(permutation)

Output:

(0, 0, 0)
(0, 0, 1)
(0, 0, 2)
(0, 1, 0)
(0, 1, 1)
# some omitted
(2, 1, 1)
(2, 1, 2)
(2, 2, 0)
(2, 2, 1)
(2, 2, 2)