不使用 itertools 的不重复排列

Question

我需要在暴力算法中获取长度为 n 的可迭代对象的所有排列。我不想使用 itertools 或任何其他外部包。

我想我可以使用 Heap 的算法，但我的代码只 returns 对 n 重复了一个排列！次数：

def permutations(l):
    n = len(l)
    result = []
    c = n * [0]
    result.append(l)
    i = 0;
    while i < n:
        if c[i] < i:
            if i % 2 == 0:
                tmp = l[0]
                l[0] = l[i]
                l[i] = tmp
            else:
                tmp = l[c[i]]
                l[c[i]] = l[i]
                l[i] = tmp
            result.append(l)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return result

我不明白为什么会这样。我也在尝试找出是否有更有效的方法来执行此操作，也许使用递归函数。

Answer 1

你可以使用下面的，这没有使用其他内部函数，但它使用了递归：

def permutation(lst):
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return [lst]

    l = [] # empty list that will store current permutation

    for i in range(len(lst)):
       m = lst[i]

       # Extract lst[i] or m from the list. remainderLst is remaining list
       remainderLst = lst[:i] + lst[i+1:]

       # Generating all permutations where m is first element
       for p in permutation(remainderLst):
           l.append([m] + p)
    return l


data = list('12345')
for p in permutation(data):
    print(p)

Answer 2

我会使用@David S 的回答。或者您可以使用此代码：

def permutate(ls):
    if len(ls) == 0: return []
    elif len(ls) == 1: return [ls]
    else:
        ls1 = []
        for i in range(len(ls)):
            x = ls[i]
            y = ls[:i] + ls[i+1:]
            for p in permutate(y): ls1.append([x]+p)
        return ls1

a = str(input("To permutate? ")).split(" ")
for i in permutate(a): print(" ".join(i))

但基本上是一样的:D

不使用 itertools 的不重复排列

Permutations without repetition without using itertools

python

permutation

heaps-algorithm