在python中替换置换的递归函数算法

Question

因此，使用itertools模块，我可以编写一段代码，用于生成所有具有替换的排列，但我想要做的事情是使用递归。

这就是我想出了：

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也会被搞乱。这怎么能够干净地工作？

我真正想做的是做一个递归，基本上取代了用替换生成所有排列的嵌套for-loop方法，我的理解是递归解决了嵌套for-loop方法需要知道深度的问题先验地嵌套for循环。所以如果有人能告诉我如何做到这一点，那也会很好，谢谢。

Answer 1

我觉得你的方法的问题是，你还没有提交，精神上的递归。警告标志在开始之前必须创建整个大小的数组，并且发现您需要知道例程递归例程体内的整个事物有多大。

我想出了通过思考以下：

1）将p_w_r的答案是什么对于k = 1和任意n？我在n = 2的纸上进行了实验

2）考虑到我认为的答案是1，我如何从k = 1的输出开始 作出k = 2的答案。

在我意识到k = 1的答案必须是单个元素列表本身的列表（当然，当你看到它时很明显）之前，我不得不在概念上弄乱一下。从那里，我可以看到我需要“将这个列表”粘贴到第k + 1个案例中的每个元素上。

 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$ 

Answer 2

我想这不会帮助，如果你想推出自己的解决方案，但有一个非常干净的方式来使用itertools.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) 

输出：

(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)