Как генерировать перестановки с ограничениями

Один из подходов - переформулировать проблему выбора перестановки для вашего неограниченного набора (["x","y","z"] в вашем примере) и выбора ее позиций на выходе, при этом позиции упорядоченного списка ([1,2,3] в вашем примере) являются оставшимися .

Например, ["z",1,"x","y",2,3] — это перестановка ["z","x","y"] и позиции [0,2,3].

Вот код для более общего ответа на вашу проблему с набором текста и проверкой, где 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

Как сказано в комментариях, существуют и другие эквивалентные переформулировки, такие как выбор перестановки, а затем выбор возрастающих (с повторениями) индексов, куда вставлять элементы упорядоченного списка.

Просматривая все наборы индексов вставки для чисел и всех перестановок букв:

from itertools import *

for I in combinations(range(6), 3):
    for [*p] in permutations('xyz'):
        *map(p.insert, I, (1, 2, 3)),
        print(p)

Вывод (сокращенно Попробуйте это онлайн!):

[1, 2, 3, 'x', 'y', 'z']
[1, 2, 3, 'x', 'z', 'y']
[1, 2, 3, 'y', 'x', 'z']
[1, 2, 3, 'y', 'z', 'x']
[1, 2, 3, 'z', 'x', 'y']
[1, 2, 3, 'z', 'y', 'x']
[1, 2, 'x', 3, 'y', 'z']
[1, 2, 'x', 3, 'z', 'y']
...
['z', 'x', 'y', 1, 2, 3]
['z', 'y', 'x', 1, 2, 3]

Тест, включающий также два решения для фильтрации, как в вашем вопросе, чтобы показать, что мы на самом деле быстрее:

 97.4 ± 0.2 μs  f1
110.1 ± 0.2 μs  Abel_Adary
217.3 ± 0.5 μs  f3
273.6 ± 0.7 μs  f2

Python: 3.12.2 (main, Jun 12 2024, 09:13:57) [GCC 14.1.1 20240522]

Код (Попробуйте это онлайн!):

def f1():
    for I in combinations(range(6), 3):
        for [*p] in permutations('xyz'):
            *map(p.insert, I, (1, 2, 3)),
            yield p

def f2():
    for p in permutations(["x","y","z",1,2,3]):
        i = p.index
        if i(1) < i(2) < i(3):
            yield p

def f3():
    for p in permutations(["x","y","z",1,2,3]):
        it = iter(p)
        1 in it
        if 2 in it and 3 in it:
            yield p

def Abel_Adary():
    return f_(["x", "y", "z"], [1,2,3])
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)


funcs = [f1, f2, f3, Abel_Adary]

from timeit import timeit
from statistics import mean, stdev
import sys
import random
from collections import deque
from itertools import *
import itertools

expect = None
for f in funcs:
    result = set(map(tuple, f()))
    if expect is None:
        expect = result
    else:
        print(result == expect)

times = {f: [] for f in funcs}
def stats(f):
    ts = [t * 1e6 for t in sorted(times[f])[:5]]
    return f'{mean(ts):5.1f} ± {stdev(ts):3.1f} μs '
consume = deque(maxlen=0).extend
for _ in range(100):
    random.shuffle(funcs)
    for f in funcs:
        t = timeit(lambda: consume(f()), number=10) / 10
        times[f].append(t)
for f in sorted(funcs, key=stats):
    print(stats(f), f.__name__)

print('\nPython:', sys.version)