射影函数集的高效计算

问：

当 的每个元素在 中至少有一个前像时，函数是射射函数。当 和 是两个有限集合时，则对应于一个数字的元组，并且当每个数字至少出现一次时，它就是投射的。（当我们要求每个数字只出现一次时，我们已经并且正在谈论排列。f : X -> YYXX = {0,...,m-1}Y = {0,...,n-1}fm< n< nn=m

我想知道一种有效的算法，用于计算两个给定数字和 的所有射射元组的集合。这些元组的数量可以通过包含-排除原则非常有效地计算（参见此处的示例），但我认为这在这里没有用（因为我们会首先计算所有元组，然后逐步删除非投射元组，并且我假设所有元组的计算将花费更长的时间*）。另一种方法如下：nm

例如，考虑元组

(1,6,4,2,1,6,0,2,5,1,3,2,3)

其中每个数字< 7 至少出现一次。看最大的 编号并擦除它：

(1,*,4,2,1,*,0,2,5,1,3,2,3)

它出现在索引 1 和 5 中，因此这对应于集合 ，索引的子集。 其余部分对应于元组{1,5}

(1,4,2,1,0,2,5,1,3,2,3)

属性< 6 的每个数字至少出现一次。

我们看到数的射射元组对应于对，其中 是 的非空子集，是数的射射 -元组，其中 有元素。m< n(T,a)T{0,...,m-1}a(m-k)< n-1Tk

这导致了以下递归实现（用 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

不过，我注意到，当输入数字很大时，这很慢。例如，当我的（旧）PC 上的计算需要几秒钟时，集合在这里有元素。我怀疑有一种更快的算法。(m,n)=(10,6)3216435440

*事实上，下面的实现非常缓慢。

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)