c++ - 根据条件枚举一组排列

Question

我已经能够使用 std::next_permutation (c++) 等解决以下问题，但我现在正在更笼统地考虑它，并且非常想形成一个表达，因为这种类型的问题似乎很适合自己 - 尽管我到目前为止还没有任何运气。

问题是:

给定一场有 N 名参赛者参加的运行比赛，恰好有 M 名参赛者获得与他们衬衫上号码相同的位置的概率是多少。其中 M <= N。

到目前为止我做了什么:

1. 会有N个!比赛结束的方式，

2. 我试过解决这个问题的一个小变体，其中包括 3 或 4 个参赛者满足条件的所需人数为 2。在这两种情况下，对于 2 人以特定顺序完成的概率为 1/2

我想知道是否已经有某种表达式可以处理所有情况？

部分代码:

#include <cstdio>
#include <algorithm>
#include <vector>

int main(int argc, char* argv[]) {
   if (argc != 3) return 1;

   int n = atoi(argv[1]);
   int m = atoi(argv[2]);

   if (m > n) return 1;

   std::vector<int> lst(n);

   for (int i = 0; i < n; ++i) lst[i] = i;

   unsigned int total = 0;
   unsigned int perm_count = 0;

   do {
      int cnt = 0;
      for (int i = 0; i < n; ++i) if (lst[i] == i) ++cnt;
      if (cnt == m) 
         ++total;
      ++perm_count;
   }
   while (std::next_permutation(lst.begin(),lst.end()));

   printf("Probability of (%d,%d) = %8.7f\n",n,m,(1.0 * total / perm_count));

   return 0;
}

更新:该表达式称为部分紊乱:

http://mathworld.wolfram.com/PartialDerangement.html

注1:如果假设完全有序的排列不算数，则公式是正确的。

注意 2:我稍微更改了问题以使其更清楚，因此也更改为代码 - 这应该与 ShreevatsaR 的评论相一致。

Answer 1

n个元素包含m个不动点的集合的排列数为

D(n,m) = \frac{n!}{m!}\sum_{k=0}^{n-m}\frac{(-1)^k}{k!} http://bit.ly/aaKqUq

(参见 http://en.wikipedia.org/wiki/Random_permutation_statistics#Number_of_permutations_that_are_derangements)

因此，概率为D(n,m)/n!，即

d(n,m) = \frac{1}{m!}\sum_{k=0}^{n-m}\frac{(-1)^k}{k!} http://bit.ly/aVqSkA