我想生成一个列表的所有可能的排列,其中循环排列(从左到右)应该只发生一次。
下面是一个例子:
设列表为[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
中是否有一种方法可以有效地解决这个问题?
3条答案
按热度按时间jucafojl1#
这是不寻常的,所以不,这不是已经在itertools。但是我们可以显著地优化你的方法(主要是通过使用 set 而不是列表来过滤掉不需要的循环,甚至只过滤掉下一个不需要的循环)。更有效的是,我们可以计算不需要的排列[*]和它们之间的
islice
的索引。查看底部的完整代码。[*]使用more-itertools的permutation_index的简化版本。
基准测试结果,使用
list(range(n))
作为序列。int比较相当快,所以如果序列元素是一些比较开销更大的对象,我的efficient
解决方案将具有更大的优势,因为它是唯一一个不依赖于比较排列/元素的解决方案。代码(Attempt This Online!):
7tofc5zh2#
权利要求:经由循环置换彼此不相关的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 [循环置换]= N Dim [与循环无关的N的置换]= N!/N =(N-1)!= Dim [N-1的所有排列]
那么你需要做的是:0.给定列表["1","2",...,"N"]
1.弹出第一个元素["2",…,"N"]
1.计算所有排列[“2”,“3”...,“N”],[“3”,“2”...,“N”]...
1.将“1”附加到每个列表[“1”,“2”,“3”…,“N”],[“1”,“3”,“2”…,“N”]…
hgb9j2n63#
请看这篇文章:Python: Generate All Permutations Subject to Condition
这个想法是从列表中提取第一个元素,生成剩余元素的所有排列,并将这些排列附加到第一个元素。