如何生成带有约束的排列

我想生成按升序排列的所有可能的 ["x","y","z",1,2,3] 列表。 “x”、“y”和“z”可以是任何实数，因此它们的顺序可以是任意的。然而，由于 1<2<3，1 必须在 2 之前，2 必须在 3 之前。因此，例如，应该生成排列 ["x", 1, "y", "z", 2, 3] ，但不应生成排列 ["x", 1, "y", "z", 3, 2]。

最简单的解决方案是

for p in itertools.permutations(["x","y","z",1,2,3]):
    if permutation_satisfies_the_constraint(p):
        yield p

但效率非常低，因为它会生成许多不需要的排列 _{（6个元素的排列总数为6！= 720，但合法排列总数为6！/3！= 120）。}

什么是仅生成以下排列的有效方法？满足1,2,3的约束？

可以通过将数字的生成与字母的生成分开来有效地生成满足约束的排列。以下是使用 Python 中的 itertools 库完成此操作的方法：

import itertools

def generate_permutations(letters, numbers):
  """
  生成满足约束的排列。

  Args:
    letters: 字符列表。
    numbers: 数字列表（已排序）。

  Yields:
    满足约束的排列。
  """
  for letter_perm in itertools.permutations(letters):
    for i in range(len(letter_perm) + 1):
      yield letter_perm[:i] + tuple(numbers) + letter_perm[i:]

# 示例用法
letters = ["x", "y", "z"]
numbers = [1, 2, 3]
for perm in generate_permutations(letters, numbers):
  print(perm)

解释：

1. 生成字母排列： 首先，使用 itertools.permutations(letters) 生成字母 "x"、"y" 和 "z" 的所有可能排列。

2. 插入数字： 对于每个字母排列，在排列中的每个可能位置插入排序的数字序列 (1, 2, 3)。这确保了数字始终按正确的顺序排列。

3. 使用 yield 进行高效生成： generate_permutations 函数使用 yield 关键字，使其成为生成器函数。这意味着它不会一次生成所有排列，而是在需要时生成它们，从而节省内存并提高效率。

效率：

此方法通过仅生成满足约束的排列来避免生成不必要的排列。复杂度主要由字母排列的数量决定，即 len(letters)! ，这比生成所有排列并随后过滤它们要有效得多。