0

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

Improve this question

3 Answers 3

Reset to default
2

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$
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

You don't need a special case for k==1 if you change k==0 to return [[]].
Thanks!!! I was actually mulling over how to get rid of that special case for ages :) And there it was in front of me the whole time. But, interestingly, spotting it requires thinking about how the whole thing works in a different way ... I was stuck on the idea that the base of it all is the generation of the n vales at k=1! Nice one!
1

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)
Improve this answer

3 Comments

If you had read the first line of my post you would have seen that I originally did it using itertools, on the other hand, thank you for acknowledging my existence, I'm so lonely =(.
@pajamas Well, yes, I read the first line of your post, but seeing as you didn't actually show us your itertools implementation, I had no way of knowing whether or not you were aware of itertools.product.
@seshin You're right, I probably should have put that implementation in there too.
0

Itertool functions would be simpler and faster, but since you’re looking for a recursive approach, I suggest we use modern Python features like yield and yield from to write a recursive generator that gets evaluated lazily (an itertool function generally returns a generator too). This implementation is efficient in both memory and time as it uses just a single preallocated list:

def permutations_with_replacement(k, n):
    perm = [-1] * k  # preallocates the single list with dummy values
    yield from perm_recursive(k, n, perm)  # do all the recursion with this list

def perm_recursive(k, n, perm):
    if k == 0:  # k is at the end (stop condition) so we can yield the list
        yield perm
    else:
        k -= 1  # we use k as index, move it one step
        for i in range(n):  # for each possible value
            perm[k] = i  # assign the value at index k
            yield from perm_recursive(k, n, perm)  # repeat for all indices

generator = permutations_with_replacement(4, 3)  # returns a generator
for p in generator:  # lazily loop over each value of the generator
    print(p)  # gives the same list, but updated by perm_recursive() each time

The result is:

[0, 0, 0, 0]
[1, 0, 0, 0]
[2, 0, 0, 0]
[0, 1, 0, 0]
[1, 1, 0, 0]
[2, 1, 0, 0]
...
[0, 1, 2, 2]
[1, 1, 2, 2]
[2, 1, 2, 2]
[0, 2, 2, 2]
[1, 2, 2, 2]
[2, 2, 2, 2]
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.