为什么Python的这种经过修改的Cartesian Product函数不起作用？

理想情况下，输入是[1,2]，输出是所有组合[[1,1]，[2,2]，[1,2]，[2,1]]。基本上，打印所有可能的组合与替换。为什么Python的这种经过修改的Cartesian Product函数不起作用？

def cart(lst): 
    if lst == []: 
     return [[]] 

    return [x[i:] + [lst[0]] + x[:i] for x in cart(lst[1:]) for i in range(len(x)) ] 

l = [1,2,3] 
print cart(l)

[]

在多个人类可读的形式，代码基本上说：

for x in cart(lst[1:]): 
    for i in range(len(x)): 
     return x[i:] + [lst[0]] + x[:i]

如果我们假设与输入递归情况下[1,2,3]，然后 cart([2,3]) s将产生[[2,3], [3,2], [2,2], [3,3]]，因此对于递归步骤，我们想要在每个可能的位置插入1。（此代码可能缺少111的情况。）

该代码在逻辑上显示正确，但输出空字符串。

有什么遗漏或我不正确地接近问题？

编辑

其实，我认识的代码会稍微复杂一些：

def cart(lst): 
    if len(lst) <= 1: 
     return lst 
    else: 
     return [x[i:] + [lst[j]] + x[:i] for x in cart(lst[1:]) for j in range(len(lst)) for i in range(len(x))]

虽然这仍然奇怪返回一个空列表。我的直觉是我错过了一个基本案例。

编辑

这是一件与我的基本情况。修改后的代码：

def cart(lst): 
    if len(lst) <= 1: 
     return [lst] 
    else: 
     return [x[i:] + [lst[j]] + x[:i] for x in cart(lst[1:]) for j in range(len(lst)) for i in range(len(x))] 

l = [1,2,3] 
print cart(l)

但现在返回

[[3，2，1]，[2，1,3]，[3,2，2]，[2，2,3 ]，[3,2,3]，[2,3,3]，[3,3,1,]，[3,1,3]，[3,3,2]，[3,2,3] ，[3，3，3]，[3，3，3]]

现在更好了，尽管输出缺少集合。似乎又是一个基本案例问题。

来源

2016-02-11 Aspen

如果你找到了你的问题的答案，然后张贴它，并接受它。它对每个人都有好处。 –

所以你想实现itertools.product？ – Copperfield

@Copperfield是的！ – Aspen

在这里找到 Algorithm for recursive function for permutations with replacement in python

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

     if k == 1: 
      return [[n[i]] for i in range(len(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(len(n)): 
       for permutation in k_take_one_permutations: 
        result.append([n[i]]+permutation) 
      return result 

     print permutations_with_replacement(3,2) 

print permutations_with_replacement(3, [1,2,3])

看来我是想取列表本身的递归的情况下，而不是组合的大小答案。

我想知道该解决方案是否可以通过在列表上反复执行，而不是组合的大小。

来源

2016-02-11 19:01:22 Aspen

为什么Python的这种经过修改的Cartesian Product函数不起作用？

回答

相关问题