1

整数の配列を与えます。

たとえば、a = {1,2,20,19} 2 つの互いに素な部分配列を {1,2} と {20,19} とします。'1' が常に '2' の前に来て、'20' が常に '19' の前に来る 5 つの順列があります。

  1. {1、2、20、19}
  2. {1, 20, 2, 19}
  3. {1、20、19、2}
  4. {20、1、19、2}
  5. {20、19、1、2}

私の質問は:

与えられた配列、サイズ=n+m の a[1...n+m]。2 つの部分配列 a[1..n] と a[n+1..n+m] の要素の相対的な順序が同じままである順列の数を見つけます。

4

1 に答える 1

1
  1. あなたの例では、6つの順列になります。{20,1,2,19} を見逃しています。

  2. 純粋数学(組み合わせ論)の問題です。質問は次と同じです -
    方程式のすべての可能な解の数を見つけます :

    x0+x1+....+xn = m

答えは次の式で定義されます -(n+m)!/(m!n!)

たとえば、あなたの場合はそうn=m=2なり、答えは4!/2!2! = 6

于 2012-10-04T07:10:52.383 に答える