3

我们得到一个整数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 黑客杯中被问到的，现在比赛已经结束了。我看过其他人的代码，发现他们是使用DFS. 有什么帮助吗？

4

1 回答 1

2

最简单的方法是使用标准排列生成器并过滤掉每个违反条件的排列。这显然是非常低效的，并且对于较大的 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（你明白为什么吗？）。现在，我们接下来乘以下一个条件的组合，即剩余空白点（X）上的 2 < 4。我们可以相乘，因为这个条件完全独立于 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。

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

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

于 2013-02-11T19:10:08.820 回答