c++ - 给定 N-1 约束，计算小于整数 N 的数字的可能排列数

Question

给定一个整数 N，我们需要计算小于 N 的数字的排列总数。我们还给定了 N-1 约束条件。例如:

如果 N=4 则计算给定的 0,1,2,3 的排列:

0>1
0>2
0>3

我考虑制作一个图表，然后计算同一级别数字排列的总数，并将其与其他级别的排列相乘。例如:

对于上面的例子:

             0
           / |  \
          /  |   \
         1   2    3 ------> 3!=6 So total no of permutations are 6.

但我很难用C++实现它。另外，这个问题在 Facebook hacker cup 上被问过，现在比赛已经结束了。我看过其他人的代码，发现他们是使用DFS 来完成的。有帮助吗？

Answer 1

执行此操作的最简单方法是使用标准排列生成器并过滤掉每个违反条件的排列。这显然是非常低效的，并且对于较大的 N 值是不可计算的。这样做是这些比赛所具有的一种“诱杀”选项，可以让不太聪明的参赛者完成问题。

熟练的方法需要深入了解计算组合和排列的方法。为了说明该方法，我将使用一个示例。输入:

   N = 7  
   2 < 4  
   0 < 3  
   3 < 6  

我们首先通过将依赖条件合并为一个条件来简化它，如下所示:

   2 < 4  
   0 < 3 < 6  

从最长的条件开始，确定间隙的组合计数(这是关键见解)。例如，部分组合如下:

   XXXX036  
   XXX0X36  
   XXX03X6  
   XXX036X  
   XX0XX36  
   etc.  

现在，您可以看到有 4 个间隙: ? 0？ 3？ 6？我们需要计算 X 在这四个间隙中的可能分区。这样的分区数是(7选3)=35(明白为什么了吗？)。现在，我们接下来乘以下一个条件的组合，即 2 < 4 超过剩余的空白点(Xs)。我们可以相乘，因为这个条件完全独立于 0<3<6 条件。此组合计数为(4 选择 2)= 6。最终条件在 2 个位置有 2 个值 = 2! = 2。因此，答案是 35 x 6 x 2 = 420。

现在，让我们把它复杂一点。添加条件:

   1 < 6

这改变了计算的方式是 036 之前必须按该顺序出现。但是，现在，我们有三种可能的安排:

   1036  
   0136  
   0316  

因此，现在总数为(7 选择 4)x 3 x(3 选择 2)= 35 x 3 x 3 = 315。

因此，回顾一下，该过程是将问题隔离到独立的条件中。对于每个独立条件，您计算分区的组合，然后将它们相乘。

我已经手动完成了这个示例，但您可以编写相同的程序。