爲什麼Python的這種經過修改的Cartesian Product函數不起作用？

Question

理想情況下，輸入是[1,2]，輸出是所有組合[[1,1]，[2,2]，[1,2]，[2,1]]。基本上，打印所有可能的組合與替換。

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]]

現在更好了，儘管輸出缺少集合。似乎又是一個基本案例問題。

Answer 1

在這裏找到 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]) 

看來我是想取列表本身的遞歸的情況下，而不是組合的大小答案。

我想知道該解決方案是否可以通過在列表上反覆執行，而不是組合的大小。