生成n元素的k元组（k>n）：每个元素至少用一次的高效算法

首先明确你要生成的结构名称：
这种序列在组合数学里被称为n元集合上长度为k的满射有序序列，等价于从k个位置到n个元素的满射函数枚举——每个序列对应一个函数，把每个位置映射到一个元素，且所有元素都被至少映射一次。也可以通俗描述为「每个元素至少出现一次的可重复排列」。

原代码重复问题分析 #

你的代码会生成重复结果，核心原因是同一个最终序列可以通过不同的初始排列+插入位置组合生成。比如对于集合{1,2}、k=3，序列(1,1,2)既可以通过初始排列(1,2)在位置0插入1得到，也可以通过初始排列(1,2)在位置1插入1得到，这就导致了重复输出。

高效迭代算法 #

推荐采用「计数分配+唯一多重排列」的构造思路，直接生成符合要求的序列，完全避免重复，效率远高于暴力筛选或原方法：

步骤说明

1. 分配元素出现次数：先确定每个元素的出现次数，要求每个元素至少出现1次，总次数为k。这等价于把k-n个额外配额分配给n个元素（每个元素可分到0个或多个），用「隔板法」生成所有可能的次数组合。
2. 生成唯一多重排列：对每个次数组合，生成该多重集合的所有唯一有序排列，避免重复。

实现代码

import itertools

def multiset_permutations(multiset):
    """生成多重集合的唯一排列，避免重复"""
    sorted_ms = sorted(multiset)
    n = len(sorted_ms)
    used = [False] * n

    def backtrack(path):
        if len(path) == n:
            yield tuple(path)
            return
        for i in range(n):
            if used[i]:
                continue
            # 跳过重复元素的重复排列
            if i > 0 and sorted_ms[i] == sorted_ms[i-1] and not used[i-1]:
                continue
            used[i] = True
            path.append(sorted_ms[i])
            yield from backtrack(path)
            path.pop()
            used[i] = False

    yield from backtrack([])

def generate_surjective_sequences(input_set, k):
    n = len(input_set)
    if k < n:
        raise ValueError("k必须大于等于集合元素数量n")
    if k == n:
        yield from itertools.permutations(input_set)
        return
    
    elements = list(input_set)
    
    # 用隔板法生成所有元素出现次数的组合（每个元素至少1次，总和为k）
    for partitions in itertools.combinations(range(k-1), n-1):
        counts = []
        prev = -1
        for p in partitions:
            counts.append(p - prev)
            prev = p
        counts.append((k-1) - prev)
        
        # 构建对应的多重集合
        multiset = []
        for elem, cnt in zip(elements, counts):
            multiset.extend([elem] * cnt)
        
        # 生成该多重集合的所有唯一排列
        yield from multiset_permutations(multiset)

代码优势

• 无重复输出：通过回溯生成唯一多重排列，从根源避免重复。
• 效率更高：直接构造符合条件的序列，无需生成冗余序列再筛选，时间复杂度远低于暴力法。
• 兼容性好：支持任意k≥n的场景，包括k=n时退化为普通排列的情况。

内容的提问来源于stack exchange，提问作者PPenguin