如何生成列表的所有排列?例如:
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]
当前回答
在我看来,一个很明显的方式可能是:
def permutList(l):
if not l:
return [[]]
res = []
for e in l:
temp = l[:]
temp.remove(e)
res.extend([[e] + r for r in permutList(temp)])
return res
其他回答
如果有人喜欢这个丑陋的单行线(虽然只适用于字符串):
def p(a):
return a if len(a) == 1 else [[a[i], *j] for i in range(len(a)) for j in p(a[:i] + a[i + 1:])]
另一种方法(无libs)
def permutation(input):
if len(input) == 1:
return input if isinstance(input, list) else [input]
result = []
for i in range(len(input)):
first = input[i]
rest = input[:i] + input[i + 1:]
rest_permutation = permutation(rest)
for p in rest_permutation:
result.append(first + p)
return result
输入可以是字符串或列表
print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))
对于性能,一个由Knuth启发的numpy解决方案(第22页):
from numpy import empty, uint8
from math import factorial
def perms(n):
f = 1
p = empty((2*n-1, factorial(n)), uint8)
for i in range(n):
p[i, :f] = i
p[i+1:2*i+1, :f] = p[:i, :f] # constitution de blocs
for j in range(i):
p[:i+1, f*(j+1):f*(j+2)] = p[j+1:j+i+2, :f] # copie de blocs
f = f*(i+1)
return p[:n, :]
复制大量内存可节省时间-它比列表(itertools.permutations(range(n))快20倍:
In [1]: %timeit -n10 list(permutations(range(10)))
10 loops, best of 3: 815 ms per loop
In [2]: %timeit -n100 perms(10)
100 loops, best of 3: 40 ms per loop
这是初始排序后生成排列的渐近最优方式O(n*n!)。
有n个!最多进行一次置换,且具有下一次置换(..),以O(n)时间复杂度运行
在3个步骤中,
找到最大的j,使a[j]可以增加以最小可行量增加a[j]找到扩展新a[0..j]的字典最少方法
'''
Lexicographic permutation generation
consider example array state of [1,5,6,4,3,2] for sorted [1,2,3,4,5,6]
after 56432(treat as number) ->nothing larger than 6432(using 6,4,3,2) beginning with 5
so 6 is next larger and 2345(least using numbers other than 6)
so [1, 6,2,3,4,5]
'''
def hasNextPermutation(array, len):
' Base Condition '
if(len ==1):
return False
'''
Set j = last-2 and find first j such that a[j] < a[j+1]
If no such j(j==-1) then we have visited all permutations
after this step a[j+1]>=..>=a[len-1] and a[j]<a[j+1]
a[j]=5 or j=1, 6>5>4>3>2
'''
j = len -2
while (j >= 0 and array[j] >= array[j + 1]):
j= j-1
if(j==-1):
return False
# print(f"After step 2 for j {j} {array}")
'''
decrease l (from n-1 to j) repeatedly until a[j]<a[l]
Then swap a[j], a[l]
a[l] is the smallest element > a[j] that can follow a[l]...a[j-1] in permutation
before swap we have a[j+1]>=..>=a[l-1]>=a[l]>a[j]>=a[l+1]>=..>=a[len-1]
after swap -> a[j+1]>=..>=a[l-1]>=a[j]>a[l]>=a[l+1]>=..>=a[len-1]
a[l]=6 or l=2, j=1 just before swap [1, 5, 6, 4, 3, 2]
after swap [1, 6, 5, 4, 3, 2] a[l]=5, a[j]=6
'''
l = len -1
while(array[j] >= array[l]):
l = l-1
# print(f"After step 3 for l={l}, j={j} before swap {array}")
array[j], array[l] = array[l], array[j]
# print(f"After step 3 for l={l} j={j} after swap {array}")
'''
Reverse a[j+1...len-1](both inclusive)
after reversing [1, 6, 2, 3, 4, 5]
'''
array[j+1:len] = reversed(array[j+1:len])
# print(f"After step 4 reversing {array}")
return True
array = [1,2,4,4,5]
array.sort()
len = len(array)
count =1
print(array)
'''
The algorithm visits every permutation in lexicographic order
generating one by one
'''
while(hasNextPermutation(array, len)):
print(array)
count = count +1
# The number of permutations will be n! if no duplicates are present, else less than that
# [1,4,3,3,2] -> 5!/2!=60
print(f"Number of permutations: {count}")
#!/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在《计算机算法》一书中提出的算法。