生成所有具有最大值爲n-1的n列表，並且沒有遞歸python

Question

我想要生成n列表的所有排列，n列表的最大值爲n-1，例如，對於n = 3，所有可能的清單如下

[0,0,0] 
[0,0,1] 
[0,0,2] 
[0,1,0] 
[0,1,1] 
[0,1,2] 
[0,2,0] 
... 
[2,2,2] 

我意識到這非常迅速地增長非常大（有n^n個排列）。我現在有一個使用遞歸

def generatePermutations(allPerms, curPerm, curIndex, n): 
    #allPerms is a reference to the full set of permutations 
    #curIndex is the index which is currently being changed 
    if (curIndex == n - 1): 
     for i in range(n): 
      curPerm[curIndex] = i 
      allPerms.append(list(curPerm)) 
    else: 
     for i in range(n): 
      curPerm[curIndex] = i 
      #recursively generate all permutations past our curIndex 
      generatePermutations(allPerms, curPerm, curIndex + 1, n) 

allPermutations = [] 
currentPermutation = [] 
n = 4 
for i in range(n): 
    currentPermutation.append(0) 

generatePermutations(allPermutations, currentPermutation, 0, n) 

在試圖找到一個非遞歸的解決方案，我碰了壁，我想下面的工作代碼也必須是嵌套的循環n號，我無法弄清楚如何爲任意n做。我唯一的想法是做一些花式的添加包含循環的列表以便以某種方式運行，或者甚至更荒謬，通過編程生成代碼並將它傳遞給eval調用。我的直覺告訴我這些比必要的更復雜。任何人都可以想出解決方案嗎？謝謝！

Answer 1

簡單的方法，用庫調用：

import itertools 

def lists(n): 
    return itertools.product(xrange(n), repeat=n) 

這將返回一個迭代器，而不是一個列表。你可以通過調用list來得到一個清單。

如果你想這樣做，沒有工作強加於到itertools，你可以在基地n算，增加了最後一位，只要攜帶你打n：

def lists(n): 
    l = [0]*n 
    while True: 
     yield l[:] 
     for i in reversed(xrange(n)): 
      if l[i] != n-1: 
       break 
      l[i] = 0 
     else: 
      # All digits were n-1; we're done 
      return 
     l[i] += 1 

Answer 2

您可以使用itertools.permutations()來處理整個問題對你來說，一氣呵成：

from itertools import permutations 

allPermutations = list(permutations(range(4)) 

文檔包括Python代碼，詳細說明替代實現的Python爲該功能;使用itertools.product()一個版本，例如：

from itertools import product 

def permutations(iterable, r=None): 
    pool = tuple(iterable) 
    n = len(pool) 
    r = n if r is None else r 
    for indices in product(range(n), repeat=r): 
     if len(set(indices)) == r: 
      yield tuple(pool[i] for i in indices) 

然而，你的預期產出只是range(3)超過3 產品：

>>> from itertools import product 
>>> for p in product(range(3), repeat=3): 
...  print p 
... 
(0, 0, 0) 
(0, 0, 1) 
(0, 0, 2) 
(0, 1, 0) 
(0, 1, 1) 
(0, 1, 2) 
(0, 2, 0) 
(0, 2, 1) 
(0, 2, 2) 
(1, 0, 0) 
(1, 0, 1) 
(1, 0, 2) 
(1, 1, 0) 
(1, 1, 1) 
(1, 1, 2) 
(1, 2, 0) 
(1, 2, 1) 
(1, 2, 2) 
(2, 0, 0) 
(2, 0, 1) 
(2, 0, 2) 
(2, 1, 0) 
(2, 1, 1) 
(2, 1, 2) 
(2, 2, 0) 
(2, 2, 1) 
(2, 2, 2) 

排列組合是多短序列：

>>> from itertools import permutations 
>>> for p in permutations(range(3)): 
...  print p 
... 
(0, 1, 2) 
(0, 2, 1) 
(1, 0, 2) 
(1, 2, 0) 
(2, 0, 1) 
(2, 1, 0)