如何生成列表的所有排列?例如:
permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
如何生成列表的所有排列?例如:
permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
当前回答
注意,该算法具有n个阶乘时间复杂度,其中n是输入列表的长度
打印跑步结果:
global result
result = []
def permutation(li):
if li == [] or li == None:
return
if len(li) == 1:
result.append(li[0])
print result
result.pop()
return
for i in range(0,len(li)):
result.append(li[i])
permutation(li[:i] + li[i+1:])
result.pop()
例子:
permutation([1,2,3])
输出:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
其他回答
此解决方案实现了一个生成器,以避免在内存中保留所有排列:
def permutations (orig_list):
if not isinstance(orig_list, list):
orig_list = list(orig_list)
yield orig_list
if len(orig_list) == 1:
return
for n in sorted(orig_list):
new_list = orig_list[:]
pos = new_list.index(n)
del(new_list[pos])
new_list.insert(0, n)
for resto in permutations(new_list[1:]):
if new_list[:1] + resto <> orig_list:
yield new_list[:1] + resto
为了节省您可能的搜索和实验时间,下面是Python中的非递归置换解决方案,它也适用于Numba(从0.41版开始):
@numba.njit()
def permutations(A, k):
r = [[i for i in range(0)]]
for i in range(k):
r = [[a] + b for a in A for b in r if (a in b)==False]
return r
permutations([1,2,3],3)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
要给人留下绩效印象:
%timeit permutations(np.arange(5),5)
243 µs ± 11.1 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
time: 406 ms
%timeit list(itertools.permutations(np.arange(5),5))
15.9 µs ± 8.61 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
time: 12.9 s
因此,只有在必须从njit函数调用它时才使用此版本,否则更倾向于itertools实现。
#!/usr/bin/env python
def perm(a, k=0):
if k == len(a):
print a
else:
for i in xrange(k, len(a)):
a[k], a[i] = a[i] ,a[k]
perm(a, k+1)
a[k], a[i] = a[i], a[k]
perm([1,2,3])
输出:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
当我交换列表的内容时,需要一个可变的序列类型作为输入。例如,烫发(list(“ball”)会起作用,而烫发(“ball”)不会起作用,因为你不能更改字符串。
这种Python实现的灵感来自Horowitz、Sahni和Rajasekeran在《计算机算法》一书中提出的算法。
以下代码是给定列表的就地排列,作为生成器实现。由于它只返回对列表的引用,因此不应在生成器外部修改列表。该解决方案是非递归的,因此使用了低内存。还可以很好地处理输入列表中元素的多个副本。
def permute_in_place(a):
a.sort()
yield list(a)
if len(a) <= 1:
return
first = 0
last = len(a)
while 1:
i = last - 1
while 1:
i = i - 1
if a[i] < a[i+1]:
j = last - 1
while not (a[i] < a[j]):
j = j - 1
a[i], a[j] = a[j], a[i] # swap the values
r = a[i+1:last]
r.reverse()
a[i+1:last] = r
yield list(a)
break
if i == first:
a.reverse()
return
if __name__ == '__main__':
for n in range(5):
for a in permute_in_place(range(1, n+1)):
print a
print
for a in permute_in_place([0, 0, 1, 1, 1]):
print a
print
常规实现(无收益-将在内存中完成所有操作):
def getPermutations(array):
if len(array) == 1:
return [array]
permutations = []
for i in range(len(array)):
# get all perm's of subarray w/o current item
perms = getPermutations(array[:i] + array[i+1:])
for p in perms:
permutations.append([array[i], *p])
return permutations
产量实施:
def getPermutations(array):
if len(array) == 1:
yield array
else:
for i in range(len(array)):
perms = getPermutations(array[:i] + array[i+1:])
for p in perms:
yield [array[i], *p]
基本思想是在第一个位置遍历数组中的所有元素,然后在第二个位置遍历所有其他元素,而没有为第一个位置选择的元素,等等。您可以使用递归来实现这一点,其中停止条件是到达一个由1个元素组成的数组,在这种情况下,您返回该数组。