如何生成列表的所有排列?例如:
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 permutation(flag, k =1 ):
N = len(flag)
for i in xrange(0, N):
if flag[i] != 0:
continue
flag[i] = k
if k == N:
print flag
permutation(flag, k+1)
flag[i] = 0
permutation([0, 0, 0])
其他回答
对于Python 2.6及以上版本:
import itertools
itertools.permutations([1, 2, 3])
这将作为生成器返回。使用列表(排列(xs))作为列表返回。
免责声明:无耻的插件由包作者。:)
trotter包与大多数实现的不同之处在于,它生成的伪列表实际上不包含排列,而是描述排列与排序中各个位置之间的映射,从而可以处理非常大的排列“列表”,如本演示所示,它在一个包含字母表中所有字母排列的伪列表中执行相当即时的操作和查找,而不使用比典型网页更多的内存或处理。
在任何情况下,要生成排列列表,我们可以执行以下操作。
import trotter
my_permutations = trotter.Permutations(3, [1, 2, 3])
print(my_permutations)
for p in my_permutations:
print(p)
输出:
A pseudo-list containing 6 3-permutations of [1, 2, 3]. [1, 2, 3] [1, 3, 2] [3, 1, 2] [3, 2, 1] [2, 3, 1] [2, 1, 3]
这是受Haskell实现使用列表理解的启发:
def permutation(list):
if len(list) == 0:
return [[]]
else:
return [[x] + ys for x in list for ys in permutation(delete(list, x))]
def delete(list, item):
lc = list[:]
lc.remove(item)
return lc
常规实现(无收益-将在内存中完成所有操作):
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个元素组成的数组,在这种情况下,您返回该数组。
生成所有可能的排列
我正在使用python3.4:
def calcperm(arr, size):
result = set([()])
for dummy_idx in range(size):
temp = set()
for dummy_lst in result:
for dummy_outcome in arr:
if dummy_outcome not in dummy_lst:
new_seq = list(dummy_lst)
new_seq.append(dummy_outcome)
temp.add(tuple(new_seq))
result = temp
return result
测试用例:
lst = [1, 2, 3, 4]
#lst = ["yellow", "magenta", "white", "blue"]
seq = 2
final = calcperm(lst, seq)
print(len(final))
print(final)