使用 itertools 限制排列

Question

我正在编写一个工具，希望从 13 个字符长的列表中生成所有可能的对。每对必须交换其第二个元素。即从列表 ABCDEFGHIJKLM 我想生成诸如 AB CD、AB CE 或 CD GK.

之类的对

我正在使用 itertools.permutations 进行此操作并且有效：

perm_pairs = itertools.permutations(my_list, 4)

我计划迭代 perm_pairs 并在单独的程序中使用这些对。但是由于顺序不重要，后面的过程时间复杂度高，所以想通过防止pair inversion来提高效率。即如果我已经有 AB CD 我不想生成 CD AB.

itertools.combinations() 不会生成所有必需的对，但 itertools.permeations() 生成的对比迭代所需的多 4 倍。

是否有可以避免产生倒置的“中间方法”？

Answer 1

您可以对每对字母使用 itertools.permutations，然后检查某些字母对的逆对是否已经存在 (perm_pairs):

from itertools import permutations

my_list = "ABCDEFGHIJKLM"

perm_pairs = set()

for pair_1 in permutations(my_list, 2):
  for pair_2 in permutations((c for c in my_list if c not in pair_1), 2):
    if pair_2 + pair_1 not in perm_pairs:
      perm_pairs.add(pair_1 + pair_2)

使用 itertools 限制排列

Limiting permutations using itertools

python

itertools