python中置换置换的递归函数算法 [英] Algorithm for recursive function for permutations with replacement in python

问题描述

因此，使用itertools模块，我可以编写一段非常漂亮的代码来生成所有带有替换的排列，但是我想做的事情是使用递归.

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.

这是我想出的:

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)

基本上，它会排列每个排列的第一层(条目)，然后在每个后续迭代中，它会越来越快地通过0 ... n-1来获得所有组合.我举一个n = k = 3的例子，因为我必须初始化置换列表，并在函数内部对其进行初始化，导致递归时事情搞砸了.我还将范围的值设置为27而不是n ^ k，因为n ^ k在递归时也会被搞砸.如何使它干净地工作?

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?

我真正想做的是一个递归，该递归基本上用替换替换了产生所有排列的嵌套for循环方法，我的理解是，递归解决了嵌套for循环方法需要知道深度的问题.嵌套的for循环先验.因此，如果有人可以告诉我如何使用该方法，那也很好，谢谢.

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.

推荐答案

我认为您的方法存在的问题是，您在精神上并未致力于递归.警告标志必须在开始之前创建整个大小的数组，并发现您需要知道整个事情在例程递归例程的主体中有多大.

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)对于k = 1和任意n，p_w_r的答案是什么?我在纸上进行了n = 2

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

2)鉴于我认为这是对1的答案，我如何使k = 2开始的答案 从k = 1的输出.

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.

在我意识到k = 1的答案必须是一个单元素列表本身的列表之前，我不得不在概念上作一些改动(当然，当您看到它时，这是显而易见的).从那里，我可以看到我需要将列表粘贴"到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$ 

这篇关于python中置换置换的递归函数算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！