def all_perms(elements):
if len(elements) <= 1:
yield elements # Only permutation possible = no permutation
else:
# Iteration over the first element in the result permutation:
for (index, first_elmt) in enumerate(elements):
other_elmts = elements[:index]+elements[index+1:]
for permutation in all_perms(other_elmts):
yield [first_elmt] + permutation
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
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, :]
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
-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])
-3
请注意，此算法具有 n factorial 时间复杂度，其中 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()
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)
def all_perms(elements):
if len(elements) <=1:
yield elements
else:
for perm in all_perms(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)
4
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)
3
生成所有可能的排列
我正在使用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
#!/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])
def permutations(head, tail=''):
if len(head) == 0: print tail
else:
for i in range(len(head)):
permutations(head[0:i] + head[i+1:], tail+head[i])
称为：
permutations('abc')
0
我的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") )
347
此解决方案实现了一个生成器，以避免在内存中保留所有排列：
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
320
在我看来，一个非常明显的方式可能也是：
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
3
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')
def addperm(x,l):
return [ l[0:i] + [x] + l[i:] for i in range(len(l)+1) ]
def perm(l):
if len(l) == 0:
return [[]]
return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]
print perm([ i for i in range(3)])
我使用了基于factorial number system的算法 - 对于长度为n的列表，您可以按项目组合每个排列项目，从每个阶段的左侧项目中进行选择 . 第一项有n个选择，第二个项有n-1，最后一个只有一个，所以你可以使用阶乘数系统中数字的数字作为索引 . 这样，数字0到n！-1对应于字典顺序中的所有可能的排列 .
from math import factorial
def permutations(l):
permutations=[]
length=len(l)
for x in xrange(factorial(length)):
available=list(l)
newPermutation=[]
for radix in xrange(length, 0, -1):
placeValue=factorial(radix-1)
index=x/placeValue
newPermutation.append(available.pop(index))
x-=index*placeValue
permutations.append(newPermutation)
return permutations
permutations(range(3))
from itertools import product, permutations
A = ([1,2,3])
print (list(permutations(sorted(A),2)))
1
这是受使用列表理解的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
0
这种方式比我看到的替代方案更好，检查出来 .
def permutations(arr):
if not arr:
return
print arr
for idx, val in enumerate(arr):
permutations(arr[:idx]+arr[idx+1:])
17
原谅我的蟒蛇文盲，因为我赢了't be offering the solution in python. As I do not know what method python 2.6 uses to generate the permutations and eliben'一个看起来像Johnson-Trotter排列一代，你可能会在Permutations and their generation上寻找维基百科中的文章，看起来很像_555261中的不受欢迎的功能 .
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:]))
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
34
list2Perm = [1, 2.0, 'three']
listPerm = [[a, b, c]
for a in list2Perm
for b in list2Perm
for c in list2Perm
if ( a != b and b != c and a != c )
]
print listPerm
28 回答
人们确实可以迭代每个排列的第一个元素，如tzwenn的答案;我更喜欢这样写这个解决方案：
这个解决方案快了约30％，显然是由于递归结束于
len(elements) <= 1而不是0. 它还具有更高的内存效率，因为它使用生成器功能（通过yield），就像Riccardo Reyes的解决方案一样 .这是一个在列表上工作的算法，无需创建类似于Ber的@555263_解决方案的新中间列表 .
你可以在这里试试代码：http://repl.it/J9v
对于性能而言，这是一个受Knuth启发的numpy解决方案，（第22页）：
复制大块内存节省时间 - 比
list(itertools.permutations(range(n))快20倍：另一种方案：
请注意，此算法具有
n factorial时间复杂度，其中n是输入列表的长度在运行中打印结果：
例：
输出：
递归之美：
这个算法是最有效的算法，它避免了递归调用中的数组传递和操作，适用于Python 2,3：
用法：
以下代码仅适用于Python 2.6及更高版本
首先，导入
itertools：排列（订单事宜）：
组合（顺序无关紧要）：
笛卡尔积（有几个迭代）：
笛卡尔积（有一个可迭代的本身）：
我看到在这些递归函数中进行了很多迭代，而不是完全纯粹的递归...
所以对于那些不能遵守一个循环的人来说，这是一个粗略的，完全不必要的完全递归的解决方案
Starting with Python 2.6 （如果您使用的是Python 3），您可以使用 standard-library 工具：itertools.permutations .
如果您出于某种原因使用 older Python (<2.6) 或只是想知道它是如何工作的，这里有一个很好的方法，取自http://code.activestate.com/recipes/252178/：
itertools.permutations的文档中列出了几种替代方法 . 这是一个：另一个，基于
itertools.product：生成所有可能的排列
我正在使用python3.4：
测试用例：
输出：
因为我'm swapping the content of the list it'需要一个可变序列类型作为输入 . 例如 .
perm(list("ball"))将起作用perm("ball")赢得't because you can' t更改字符串 .这个Python实现的灵感来自Horowitz，Sahni和Rajasekeran的计算机算法一书中提出的算法 .
称为：
我的Python解决方案：
此解决方案实现了一个生成器，以避免在内存中保留所有排列：
在我看来，一个非常明显的方式可能也是：
输出：['abc'，'acb'，'bac'，'bca'，'cab'，'cba']
并在Python 2.6开始：
（作为生成器返回 . 使用
list(permutations(l))作为列表返回 . ）在功能风格
结果：
我使用了基于factorial number system的算法 - 对于长度为n的列表，您可以按项目组合每个排列项目，从每个阶段的左侧项目中进行选择 . 第一项有n个选择，第二个项有n-1，最后一个只有一个，所以你可以使用阶乘数系统中数字的数字作为索引 . 这样，数字0到n！-1对应于字典顺序中的所有可能的排列 .
输出：
这个方法是非递归的，但它在我的计算机上稍慢，xrange在n时引发错误！太大而无法转换为C长整数（对我来说n = 13） . 当我需要它时它已经足够了，但它不是一个很长的镜头的itertools.permutations .
对于Python，我们可以使用itertools并导入排列和组合来解决您的问题
这是受使用列表理解的Haskell实现的启发：
这种方式比我看到的替代方案更好，检查出来 .
原谅我的蟒蛇文盲，因为我赢了't be offering the solution in python. As I do not know what method python 2.6 uses to generate the permutations and eliben'一个看起来像Johnson-Trotter排列一代，你可能会在Permutations and their generation上寻找维基百科中的文章，看起来很像_555261中的不受欢迎的功能 .
在我看来，这可以在发生器中以与其他回复相同的方式使用，以显着减少内存需求 . 请记住，排列不会按字典顺序排列 .
以下代码是给定列表的就地排列，实现为生成器 . 因为它只会返回对列表的引用，不应在生成器外修改列表 . 解决方案是非递归的，因此使用低内存 . 也可以在输入列表中使用多个元素副本 .
输出：