How to generate permutations with constraints

Question

I want to generate all possible lists of ["x","y","z",1,2,3] that are ordered in ascending order. "x", "y" and "z" can be any real numbers and so their order can be arbitrary. However, as 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.

The simplest solution is

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

but it is very inefficient, as it would generate many unneeded permutations _{(the total number of permutations of 6 elements is 6!=720, but the total number of legal permutations is 6!/3!=120).}

What is an efficient way to generate only the permutations that satisfy the constraint on 1,2,3?

Answer 1

One approach is to reformulate the problem in the choice of a permutation for your unconstrained set (["x","y","z"] in your example) and the choice of its positions in the output, while the position of the ordered list ([1,2,3] in your example) are the remaining ones.

For instance, ["z",1,"x","y",2,3] is the permutation ["z","x","y"] and the positions [0,2,3].

Here is the code for a more general answer for your problem with typings and checks where free_list is your ["x","y","z"] and ordered_list is your [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

As said in the comments there are other equivalent reformulations like choosing the permutation and then choosing increasing (with repetitions) indexes where to insert the ordered list elements