如何生成列表的所有排列组合?例如:
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 pzip(c, seq):
result = []
for item in seq:
for i in range(len(item)+1):
result.append(item[i:]+c+item[:i])
return result
def perm(line):
seq = [c for c in line]
if len(seq) <=1 :
return seq
else:
return pzip(seq[0], perm(seq[1:]))
这个算法是最有效的,它避免了在递归调用中传递和操作数组,在Python 2和3中都可以使用:
def permute(items):
length = len(items)
def inner(ix=[]):
do_yield = len(ix) == length - 1
for i in range(0, length):
if i in ix: #avoid duplicates
continue
if do_yield:
yield tuple([items[y] for y in ix + [i]])
else:
for p in inner(ix + [i]):
yield p
return inner()
使用方法:
for p in permute((1,2,3)):
print(p)
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 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)
from __future__ import print_function
def perm(n):
p = []
for i in range(0,n+1):
p.append(i)
while True:
for i in range(1,n+1):
print(p[i], end=' ')
print("")
i = n - 1
found = 0
while (not found and i>0):
if p[i]<p[i+1]:
found = 1
else:
i = i - 1
k = n
while p[i]>p[k]:
k = k - 1
aux = p[i]
p[i] = p[k]
p[k] = aux
for j in range(1,(n-i)/2+1):
aux = p[i+j]
p[i+j] = p[n-j+1]
p[n-j+1] = aux
if not found:
break
perm(5)
def permute(xs, low=0):
if low + 1 >= len(xs):
yield xs
else:
for p in permute(xs, low + 1):
yield p
for i in range(low + 1, len(xs)):
xs[low], xs[i] = xs[i], xs[low]
for p in permute(xs, low + 1):
yield p
xs[low], xs[i] = xs[i], xs[low]
for p in permute([1, 2, 3, 4]):
print p
def all_insert(x, e, i=0):
return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i<len(x)+1 else []
def for_each(X, e):
return all_insert(X[0], e) + for_each(X[1:],e) if X else []
def permute(x):
return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0])
perms = permute([1,2,3])
@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
只有在必须从 njitted 函数中调用时才使用此版本,否则请优先考虑使用 itertools 实现。
import sympy
from sympy.utilities.iterables import multiset_permutations
t = [1,2,3]
p = list(multiset_permutations(t))
print(p)
# [[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])
range()
。请参阅https://dev59.com/xWQm5IYBdhLWcg3w-i9L - anhldbk'''
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}")
def calcperm(arr, size, dupes):
其中dupes
是允许每个排列中允许的重复次数。 - SeaDude