如何生成列表的所有排列?例如:
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 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
其他回答
def permutation(word, first_char=None):
if word == None or len(word) == 0: return []
if len(word) == 1: return [word]
result = []
first_char = word[0]
for sub_word in permutation(word[1:], first_char):
result += insert(first_char, sub_word)
return sorted(result)
def insert(ch, sub_word):
arr = [ch + sub_word]
for i in range(len(sub_word)):
arr.append(sub_word[i:] + ch + sub_word[:i])
return arr
assert permutation(None) == []
assert permutation('') == []
assert permutation('1') == ['1']
assert permutation('12') == ['12', '21']
print permutation('abc')
输出:['abc','acb','bac','bca','cab','cba']
递归之美:
>>> import copy
>>> def perm(prefix,rest):
... for e in rest:
... new_rest=copy.copy(rest)
... new_prefix=copy.copy(prefix)
... new_prefix.append(e)
... new_rest.remove(e)
... if len(new_rest) == 0:
... print new_prefix + new_rest
... continue
... perm(new_prefix,new_rest)
...
>>> perm([],['a','b','c','d'])
['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
['a', 'd', 'c', 'b']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
['b', 'd', 'a', 'c']
['b', 'd', 'c', 'a']
['c', 'a', 'b', 'd']
['c', 'a', 'd', 'b']
['c', 'b', 'a', 'd']
['c', 'b', 'd', 'a']
['c', 'd', 'a', 'b']
['c', 'd', 'b', 'a']
['d', 'a', 'b', 'c']
['d', 'a', 'c', 'b']
['d', 'b', 'a', 'c']
['d', 'b', 'c', 'a']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']
使用标准库中的itertools.permutations:
import itertools
list(itertools.permutations([1, 2, 3]))
从这里改编的是itertools.permutations如何实现的演示:
def permutations(elements):
if len(elements) <= 1:
yield elements
return
for perm in permutations(elements[1:]):
for i in range(len(elements)):
# nb elements[0:1] works in both string and list contexts
yield perm[:i] + elements[0:1] + perm[i:]
itertools.permutations文档中列出了两种替代方法
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = range(n)
cycles = range(n, n-r, -1)
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
另一个基于itertools.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)
我的Python解决方案:
def permutes(input,offset):
if( len(input) == offset ):
return [''.join(input)]
result=[]
for i in range( offset, len(input) ):
input[offset], input[i] = input[i], input[offset]
result = result + permutes(input,offset+1)
input[offset], input[i] = input[i], input[offset]
return result
# input is a "string"
# return value is a list of strings
def permutations(input):
return permutes( list(input), 0 )
# Main Program
print( permutations("wxyz") )
注意,该算法具有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]