我想生成一个列表的所有可能的排列，其中循环排列(从左到右)应该只发生一次。
下面是一个例子:
设列表为[A, B, C]。然后我想要像[A, C, B]这样的排列，而不是[B, C, A]，因为这将是原始列表[A, B, C]的循环排列。对于上面的列表，结果应该类似于
[A, B, C]
[A, C, B]
[B, A, C]
[C, B, A]
下面是一个最小的工作示例，从itertools使用permutations()。
from itertools import permutations
def permutations_without_cycles(seq: list):
# Get a list of all permutations
permutations_all = list(permutations(seq))
print("nAll permutations:")
for i, p in enumerate(permutations_all):
print(i, "t", p)
# Get a list of all cyclic permutations
cyclic_permutations = [tuple(seq[i:] + seq[:i]) for i in range(len(seq))]
print("nAll cyclic permutations:")
for i, p in enumerate(cyclic_permutations):
print(i, "t", p)
# Remove all cyclic permutations except for one
cyclic_permutations = cyclic_permutations[1:] # keep one cycle
permutations_cleaned = [p for p in permutations_all if p not in cyclic_permutations]
print("nCleaned permutations:")
for i, item in enumerate(permutations_cleaned):
print(i, "t", item)
def main():
seq = ["A", "B", "C"]
permutations_without_cycles(seq=seq)
if __name__ == "__main__":
main()
我想知道itertools中是否有一种方法可以有效地解决这个问题?
这是不寻常的，所以不，它不在itertools中。但是我们可以显著地优化你的方式(主要是通过使用集合而不是列表来过滤掉不需要的循环，或者甚至只使用下一个不需要的循环)。更有效的是，我们可以计算它们之间不需要的排列[*]和islice的索引。查看底部的完整代码。
[*]使用more-itertools中permutation_index的简化版本。
基准测试结果，使用list(range(n))作为序列。整型比较相当快，所以如果序列元素是一些需要更昂贵比较的对象，我的efficient解决方案将具有更大的优势，因为它是唯一不依赖于比较排列/元素的解决方案。
8 elements:
1.76 ± 0.07 ms efficient
3.60 ± 0.76 ms optimized_iter
4.65 ± 0.81 ms optimized_takewhile
4.97 ± 0.43 ms optimized_set
8.19 ± 0.31 ms optimized_generator
21.42 ± 1.19 ms original
9 elements:
13.11 ± 2.39 ms efficient
34.37 ± 2.83 ms optimized_iter
40.87 ± 4.49 ms optimized_takewhile
46.74 ± 2.27 ms optimized_set
78.79 ± 3.43 ms optimized_generator
237.72 ± 5.76 ms original
10 elements:
160.61 ± 4.58 ms efficient
370.79 ± 14.71 ms optimized_iter
492.95 ± 2.45 ms optimized_takewhile
565.04 ± 9.68 ms optimized_set
too slow optimized_generator
too slow original
代码(try This Online!):
from itertools import permutations, chain, islice, filterfalse, takewhile
from timeit import timeit
from statistics import mean, stdev
from collections import deque
# Your original, just without the prints/comments, and returning the result
def original(seq: list):
permutations_all = list(permutations(seq))
cyclic_permutations = [tuple(seq[i:] + seq[:i]) for i in range(len(seq))]
cyclic_permutations = cyclic_permutations[1:]
permutations_cleaned = [p for p in permutations_all if p not in cyclic_permutations]
return permutations_cleaned
# Your original with several optimizations
def optimized_set(seq: list):
cyclic_permutations = {tuple(seq[i:] + seq[:i]) for i in range(1, len(seq))}
return filterfalse(cyclic_permutations.__contains__, permutations(seq))
# Further optimized to filter by just the single next unwanted permutation
def optimized_iter(seq: list):
def parts():
it = permutations(seq)
yield next(it),
for i in range(1, len(seq)):
skip = tuple(seq[i:] + seq[:i])
yield iter(it.__next__, skip)
yield it
return chain.from_iterable(parts())
# Another way to filter by just the single next unwanted permutation
def optimized_takewhile(seq: list):
def parts():
it = permutations(seq)
yield next(it),
for i in range(1, len(seq)):
skip = tuple(seq[i:] + seq[:i])
yield takewhile(skip.__ne__, it)
yield it
return chain.from_iterable(parts())
# Yet another way to filter by just the single next unwanted permutation
def optimized_generator(seq: list):
perms = permutations(seq)
yield next(perms)
for i in range(1, len(seq)):
skip = tuple(seq[i:] + seq[:i])
for perm in perms:
if perm == skip:
break
yield perm
yield from perms
# Compute the indexes of the unwanted permutations and islice between them
def efficient(seq):
def parts():
perms = permutations(seq)
yield next(perms),
perms_index = 1
n = len(seq)
for rotation in range(1, n):
index = 0
for i in range(n, 1, -1):
index = index * i + rotation * (i > rotation)
yield islice(perms, index - perms_index)
next(perms)
perms_index = index + 1
yield perms
return chain.from_iterable(parts())
funcs = original, optimized_generator, optimized_set, optimized_iter, optimized_takewhile, efficient
#--- Correctness checks
seq = ["A", "B", "C"]
for f in funcs:
print(*f(seq), f.__name__)
seq = 3,1,4,5,9,2,6
for f in funcs:
assert list(f(seq)) == original(seq)
for n in range(9):
seq = list(range(n))
for f in funcs:
assert list(f(seq)) == original(seq)
#--- Speed tests
def test(seq, funcs):
print()
print(len(seq), 'elements:')
times = {f: [] for f in funcs}
def stats(f):
ts = [t * 1e3 for t in sorted(times[f])[:5]]
return f'{mean(ts):6.2f} ± {stdev(ts):5.2f} ms '
for _ in range(25):
for f in funcs:
t = timeit(lambda: deque(f(seq), 0), number=1)
times[f].append(t)
for f in sorted(funcs, key=stats):
print(stats(f), f.__name__)
test(list(range(8)), funcs)
test(list(range(9)), funcs)
test(list(range(10)), funcs[2:])
结论:N个不通过循环置换相互关联的元素的集合置换与N-1个元素的所有置换是一一对应的
不严格证明:任何排列{i1,i2，…，iN}，第k个元素ik=1，可以通过循环置换变换为{1,j2，…，jN} (j2=i(k+1)，j3=i(k+2)，…)。排列{1,j2，…，jN}唯一地表示循环排列的轨道。因此，N-1个元素{j2，…，jN}表示N个不与循环相关的元素的排列轨道。
最简单的说服自己的方法是计算维度(元素的数量):Dim[N的所有排列]= N!Dim[循环排列]= NDim[不与圈相关的N的排列]= N!/n = (n -1)!= Dim[N-1的所有排列]
那么你需要做的是:0. 给定的列表("1","2",…,"N"]
- 流行第一个元素("2",…,"N"]
- 计算所有排列("2","3"…,"N"],["3","2"…,"N"]…
- 附加"1";每个列表("1","2","3"…,"N"],["1","3"、"2"…,"N"]…
查看此帖子:Python:根据条件生成所有排列
这个想法是从列表中取出第一个元素，生成剩余的的所有排列元素并将这些排列追加到第一个元素。