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

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）。

按照你的逻辑，你会用两种方式计算它，即使它应该只计算一次，因为最终结果是一样的。等等...

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

Number of distinct sequences of fixed length which can be generated using a given set of numbers

algorithm

sequences

permutation

set

combinatorics