algorithm - 可以使用一组给定的数字生成的固定长度的不同序列的数量

Question

我试图找到固定长度的不同序列，这些序列可以使用给定集合(不同元素)中的数字生成，这样集合中的每个元素都应该出现在序列中。以下是我的逻辑:

例如。让集合由 S 个元素组成，我们必须生成长度为 K (K >= S) 的序列

1) 首先，我们必须从 K 个中选择 S 个位置，并以随机顺序放置集合中的每个元素。所以，C(K,S)*S!

2) 之后，可以用集合中的任何值填充剩余的位置。所以，因素

(K-S)^S 应该相乘。

所以，总体结果是

C(K,S)S!((K-S)^S)

但是，我得到了错误的答案。请帮忙。

PS: C(K,S) :从 K 个元素中选择 S 个元素的方式数 (K>=S)，与顺序无关。另外，^:幂符号，即 2^3 = 8。

这是我在 python 中的代码:

# m is the no. of element to select from a set of n elements
# fact is a list containing factorial values i.e. fact[0] = 1, fact[3] = 6& so on. 
def ways(m,n):
    res = fact[n]/fact[n-m+1]*((n-m)**m)
    return res

Answer 1

您正在寻找的是满射函数的数量，其定义域是一组 K 个元素(我们在输出序列中填写的 K 个位置)并且图像是一组 S 个元素(您的输入集) .我认为这应该有效:

    static int Count(int K, int S)
    {
        int sum = 0;
        for (int i = 1; i <= S; i++)
        {
            sum += Pow(-1, (S-i)) * Fact(S) / (Fact(i) * Fact(S - i)) * Pow(i, K);
        }
        return sum;
    }

...其中 Pow 和 Fact 是您所期望的。

看看这个 this math.se question .

这就是您的方法行不通的原因。我没有检查代码，只是检查了您对其背后逻辑的解释，但我很确定我理解您的尝试做。让我们以 K = 4，S = {7,8,9} 为例。让我们检查序列 7,8,9,7。这是一个独特的序列，但您可以通过以下方式获得它:

• 随机选择位置 1、2、3，用 7、8、9 随机填充它们(您的步骤 1)，然后随机选择 7 作为剩余位置 4(您的步骤 2)。

• 随机选择位置 2、3、4，用 8、9、7 随机填充它们(您的步骤 1)，然后随机选择 7 作为剩余位置 1(您的步骤 2)。

按照您的逻辑，您会两种方式都计算它，即使它应该只计算一次，因为最终结果是相同的。等等……