如何高效计算满射函数对应的所有满射元组集合？

当函数 f : X -> Y 满足Y中的每个元素在X中至少有一个原像时，该函数是满射函数。若X={0,...,m-1}、Y={0,...,n-1}为有限集，那么f对应一个由小于n的数组成的m元组——满射元组就是每个小于n的数至少出现一次的这类m元组（当n=m时，要求每个数恰好出现一次，此时就是排列）。

我需要找到一种高效算法，生成给定n和m时的所有满射元组集合：

• 容斥原理能高效计算这类元组的数量，但如果用它来生成集合，需要先生成所有元组再剔除非满射元组，效率很低。
• 我尝试过一种递归思路：每个满射m元组对应一个非空索引子集T，以及一个满射(m-k)元组a（k为T的元素个数，a由小于n-1的数组成），并实现了如下Python递归代码：

import itertools

def surjective_tuples(m: int, n: int) -> set[tuple]:
    """Set of all m-tuples of numbers < n where every number < n appears at least once.

    Arguments:
        m: length of the tuple
        n: number of distinct values
    """
    if n == 0:
        return set() if m > 0 else {()}
    if n > m:
        return set()
    result = set()
    for k in range(1, m + 1):
        smaller_tuples = surjective_tuples(m - k, n - 1)
        subsets = itertools.combinations(range(m), k)
        for subset in subsets:
            for smaller_tuple in smaller_tuples:
                my_tuple = []
                count = 0
                for i in range(m):
                    if i in subset:
                        my_tuple.append(n - 1)
                        count += 1
                    else:
                        my_tuple.append(smaller_tuple[i - count])
                result.add(tuple(my_tuple))
    return result

但这段代码在m、n较大时速度极慢，比如计算(m,n)=(10,6)时耗时32秒，对应的集合有16435440个元素。而暴力枚举所有元组再筛选的方法效率更低：

def surjective_tuples_stupid(m: int, n: int) -> list[int]:
    all_tuples = list(itertools.product(*(range(n) for _ in range(m))))
    surjective_tuples = filter(lambda t: all(i in t for i in range(n)), all_tuples)
    return list(surjective_tuples)

现寻求更快速的高效算法。

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