3

整数が与えられ、NN未満の数の順列の総数を数える必要があり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

最初に、次のように依存条件を 1 つの条件に結合することにより、これを単純化します。

   2 < 4  
   0 < 3 < 6

最長の条件から始めて、ギャップの組み合わせ数を決定します (これが重要な洞察です)。たとえば、次のような組み合わせがあります。

   XXXX036  
   XXX0X36  
   XXX03X6  
   XXX036X  
   XX0XX36  
   etc.

ここで、4 つのギャップがあることがわかります。0 ? 3 ? 6?. これらの 4 つのギャップで 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 がその順序で表示される必要があったことです。しかし、現在、3 つの可能な配置があります。

   1036  
   0136  
   0316

したがって、合計カウントは (7 が 4 を選択) x 3 x (3 が 2 を選択) = 35 x 3 x 3 = 315 になります。

つまり、要約すると、手順は問題を独立した条件に分離することです。独立した条件ごとに、パーティションの組み合わせを計算し、それらを乗算します。

この例は手動で説明しましたが、同じ手順をプログラムすることもできます。

于 2013-02-11T19:10:08.820 に答える