[Python] 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.

Here's what I came up with:

def permutations_with_replacement(n,k,permutations):
m = 0
if k < 1:
return permutations

for i in range(27):
permutations.append(m % n)
if (i % n**(k-1)) == n**(k-1) - 1:
m = m + 1

return permutations_with_replacement(n,k-1,permutations)


n = 3
k = 3
permutations = [[] for i in range(n**k)]
print permutations_with_replacement(n,k,permutations)


Basically it sort of lays the first layer (entry) of each permutation, and then upon each subsequent iteration it runs through 0...n-1 quicker and quicker in order to get all combinations. I put in an example with n=k=3 since I have to initialize the permutations list and initializing it inside the function causes things to get screwed up upon recursion. I also put in 27 for the range rather than n^k, since n^k would get screwed up as well upon recursion. How could this be made to work cleanly?

What I really wanted to do was do a recursion that basically replaced the nested for-loop method of producing all permutations with replacement, my understanding being that recursion gets around the problem that the nested for-loop method requires knowing the depth of the nested for-loops a priori. So if anyone can show me how to do it that way, that would be great as well, thanks.

Continue reading...