如何在Python中遞歸排列列表中的n個元素？

我想弄清楚如何遞歸地從列表中創建所有可能的n個大小的排列。如何在Python中遞歸排列列表中的n個元素？

。例如n=2和list=[0,1,5]結果將是：

[[0, 0], [1, 0], [5, 0], [0, 1], [1, 1], [5, 1], [0, 5], [1, 5], [5, 5]]

或n=3和list=[2,3]：

[[2, 2, 2], [3, 2, 2], [2, 3, 2], [3, 3, 2], [2, 2, 3], [3, 2, 3], [2, 3, 3], [3, 3, 3]]

（有點像笛卡兒積）。

我已經成功地拿出了這段代碼：

def perm(nlist, m): 

    if m > len(nlist): 
     return 
    if m == 0 or m == len(nlist): 
     return [[]] 
    results = []    
    for list_i in nlist: 
     temp = list(nlist)   
     temp.remove(list_i) 
     results.extend(map(lambda x: [list_i] + x, perm(temp, m-1))) 
    return results

，但它不會給像[0,0] [1,1] [2,2]等排列

是否有人對我有一個解決方案嗎？

我怎樣才能做到這一點，而不使用map()和lambda()？

來源

2015-04-30 Ran Tuchman

提示：不要使用'list'作爲名字，它是一個[內置函數（https://docs.python.org/3/library/ functions.html＃FUNC列表）。 –

你有沒有考慮過使用[itertools.permutations]（https://docs.python.org/2/library/itertools.html#itertools.permutations）？ –

[如何在Python中生成列表的所有排列]可能的重複（http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python） –

這不是排序像笛卡爾積;它是，正像一樣喜歡笛卡爾產品。

>>> from itertools import product 
>>> list(product([0,1,5], repeat=2)) 
[(0, 0), (0, 1), (0, 5), (1, 0), (1, 1), (1, 5), (5, 0), (5, 1), (5, 5)] 
>>> list(product([2,3], repeat=3)) 
[(2, 2, 2), (2, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (3, 3, 2), (3, 3, 3)]

的填充工具爲itertools.product如下：

def product(*args, **kwds): 
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy 
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111 
    pools = map(tuple, args) * kwds.get('repeat', 1) 
    result = [[]] 
    for pool in pools: 
     result = [x+[y] for x in result for y in pool] 
    for prod in result: 
     yield tuple(prod)

但既然你不能使用itertools，您不妨來寫一個稍微更有效的解決問題的方法的自由。因爲我們只是計算的n相同iterables的產品，就讓我們把它叫做笛卡爾指數：

def cartesian_exponent(li, e=1): 
    pools = [li] * e 
    result = [[]] 
    for pool in pools: 
     result = [x+[y] for x in result for y in pool] 
    return result

或者遞歸使用另一個難以理解的列表理解：

def cartesian_exponent(li, e=1): 
    if e == 1: 
     return [[x] for x in li] 
    else: 
     return [[x]+y for x in li for y in cartesian_exponent(li, e=e-1)]

哪些可以被壓縮到一個線：

def cartesian_exponent(li, e=1): 
    return [[x] for x in li] if e == 1 else [[x] + y for x in li for y in cartesian_exponent(li, e=e-1)]

但是，那麼你會犧牲可讀性的簡潔，這是沒有bueno。不可理解的列表理解已經不夠透徹。

一些測試：

>>> cartesian_exponent([0,1,5], e=2) 
[[0, 0], [0, 1], [0, 5], [1, 0], [1, 1], [1, 5], [5, 0], [5, 1], [5, 5]] 
>>> cartesian_exponent([2,3], e=3) 
[[2, 2, 2], [2, 2, 3], [2, 3, 2], [2, 3, 3], [3, 2, 2], [3, 2, 3], [3, 3, 2], [3, 3, 3]]

來源

2015-04-30 15:45:38 Shashank

我喜歡它的簡單，但即時尋找一個遞歸解決方案。 thx –

@runtuchman遞歸解決方案已添加到我的答案。 – Shashank

如何在沒有列表解析的情況下編寫此代碼？ –

您正在查找的結果是Cartesian product，它是所有有序對（a，b）的集合，其中a∈A且b∈B。或者，所有組合的所有排列。

from itertools import combinations_with_replacement as iter_combs 
from itertools import permutations 

def perms_combs(l, n): 
    all_combs = [] 
    for l in list(iter_combs(l, n)): 
      [all_combs.append(perm) for perm in list(permutations(l, n))] 
    return list(set(all_combs))

>> print list(product([0, 1, 5], repeat=2)) 
    [(0, 0), (0, 0), (0, 1), (1, 0), (0, 5), (5, 0), (1, 1), (1, 1), (1, 5), (5, 1), (5, 5), (5, 5)] 

>> print list(product([2, 3], repeat=3)) 
    [(3, 3, 3), (2, 2, 2), (2, 3, 2), (3, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (2, 2, 3)]

該過程，然而，已經涵蓋由itertools功能：product

from itertools import product 

>> print product([0, 1, 5], 2) 
    [(0, 0), (0, 0), (0, 1), (1, 0), (0, 5), (5, 0), (1, 1), (1, 1), (1, 5), (5, 1), (5, 5), (5, 5)] 

>> print product([2, 3], 3) 
    [(3, 3, 3), (2, 2, 2), (2, 3, 2), (3, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (2, 2, 3)]

來源

2015-04-30 14:54:29

如何在Python中遞歸排列列表中的n個元素？

回答

相關問題