如何生成带约束的排列

Question

我想生成所有可能的 ["x","y","z",1,2,3] 列表，并按升序排列。 “x”、“y”和“z”可以是任何实数，因此它们的顺序可以是任意的。然而，正如 1<2<3, 1 must be before 2 and 2 must be before 3. So, for example, the permutation ["x", 1, "y", "z", 2, 3] should be generated, but the permutation ["x", 1, "y", "z", 3, 2] should not be generated.

最简单的解决方案是

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 约束的排列的有效方法是什么？

Answer 1

一种方法是重新表达无约束集（在您的情况下为 x，y，z）的排列选择及其在输出中的位置选择中的问题。

这里是针对您的打字和检查问题的更一般答案的代码，其中

free_list

是您的 x、y、z，

ordered_list

是您的 1,2,3:

import itertools
from typing import Generator

def f(free_list: list[str], ordered_list: list[float]) -> Generator[tuple[str|float, ...], None, None]:
    assert len(set(free_list)) == len(free_list), "free_list should have unique elements"
    assert all(x < y for x,y in zip(ordered_list[:-1], ordered_list[1:])), "ordered_list should be strictly increasing"
    out_len: int = len(free_list) + len(ordered_list)
    
    # Choosing a permutation of free_list
    for free_list_permutation in itertools.permutations(range(len(free_list))):
        # Choosing its place in the output
        for free_list_index_in_out in itertools.combinations(range(out_len), len(free_list)):
            out: list[str | float] = []
            
            # Inserting ordered_list and free_list at their place 
            n_free_list_inserted: int = 0
            for i in range(out_len):
                if i in free_list_index_in_out:
                    out.append(free_list[free_list_permutation[n_free_list_inserted]])
                    n_free_list_inserted += 1
                else:
                    out.append(ordered_list[i - n_free_list_inserted])
            
            yield tuple(out)
        

result = list(f(["x", "y", "z"], [1,2,3]))
assert len(result) == 120
assert len(result) == len(set(result))  # Checking uniqueness of results
for element in result:
    assert len(element) == len(set(element))  # Checking uniqueness in one result
    only_ints = [x for x in result if isinstance(x, int)]
    assert sorted(only_ints) == only_ints  # Checking ordering