20

SPOJ Problem 64: Permutationsを効率的に解決しようとしています。

A = [a1,a2,...,an] を整数 1,2,...,n の順列とする。インデックス (i,j) のペア、1<=i<=j<=n は、ai>aj の場合、順列 A の反転です。整数 n>0 および k>=0 が与えられます。正確に k 回の反転を含む n 要素置換の数は?

たとえば、反転が 1 つだけの 4 要素順列の数は 3 に等しくなります。

与えられた例を見やすくするために、正確に 1 つの反転を持つ 3 つの 4 要素順列を次に示します。

(1, 2, 4, 3)
(1, 3, 2, 4)
(2, 1, 3, 4)

最初の順列では、4 > 3 であり、4 のインデックスは 3 のインデックスよりも小さいです。これは単一の反転です。順列にはちょうど 1 つの反転があるため、数えようとしている順列の 1 つです。

n 要素の任意のシーケンスについて、順列の数は factorial(n) です。したがって、各順列の反転の数をカウントし、それらが k に等しいかどうかを確認するというブルート フォース n 2の方法を使用すると、この問題の解決策の時間計算量は O(n! * n 2 ) になります。

これまでの研究

この問題の副次的問題は、以前ここStackOverflow で尋ねられました。マージソートを使用した O(n log n) ソリューションが与えられました。これは、単一の順列での反転の数をカウントします。ただし、そのソリューションを使用して各順列の反転の数をカウントすると、O(n! * n log n) の時間の複雑さが得られますが、これは私の意見では依然として非常に高いです。

この正確な質問は、以前にスタック オーバーフローでも尋ねられましたが、回答がありませんでした。

私の目標は、すべての順列を反復することから生じる階乗の複雑さを回避することです。理想的には、任意の n と k についてこれに対する答えが得られる数式が必要ですが、存在するかどうかはわかりません。

これを解決するための数式が存在しない場合 (私は疑問に思っています)、効率的な動的計画法の解決策が可能であるというヒントを与えている人々も見てきました。DP または別のアプローチを使用して、O(n! * n log n) よりも効率的なソリューションを作成したいと思っていますが、どこから始めればよいかわかりません。

ヒント、コメント、または提案は大歓迎です。

編集:マホニアン数を計算するための DP アプローチを使用して、以下の問題に回答しました。

4

5 に答える 5

6

動的計画法の解決策がある場合、長さ n の順列の結果を使用して、長さ n+1 の順列の結果を支援することで、段階的に実行する方法がおそらくあるでしょう。

長さ n - 値 1 ～ n の順列が与えられた場合、n+1 の可能な位置で値 (n+1) を追加することにより、長さ n+1 の順列を取得できます。(n+1) は 1-n のいずれよりも大きいため、これを行うときに作成する反転の数は、追加する場所によって異なります。最後の位置に追加し、反転を作成せず、最後から 2 つ後に追加します。 n=4 のケースを 1 回の反転で振り返り、これを確認します。

したがって、(n+1) を追加できる n+1 の場所の 1 つを考慮すると、右から数えて j 番目の場所に追加すると、最後の位置が 0 の位置として、これが作成する K 反転の順列の数はn 個の場所での Kj 反転による順列。

したがって、各ステップで、可能なすべての K に対して K 反転の順列の数を数えると、長さ n の K 反転の順列の数を使用して、長さ n+1 の K 反転の順列の数を更新できます。

于 2013-10-15T04:53:31.630 に答える
-1

これらの係数を計算する際の主な問題は、結果の製品の次数のサイズです。多項積 i=1,2,..,n {(1+x).(1+x+x^2)....(1+x+x^2+..+x^i)+ ...(1+x+x^2+...+x^n) は、n*(n+1) と同等の順序になります。その結果、これはプロセスに制限的な計算制限を課します。n-1 の Product の以前の結果が n の Product の計算プロセスで使用されるプロセスを使用する場合、(n-1)*n 整数のストレージを調べています。再帰プロセスを使用することは可能ですが、これははるかに遅くなります。また、整数の一般的なサイズの平方根よりも小さい整数に制限されます。以下は、この問題に対する大まかな再帰コードです。関数 mahonian(r,c) は、r 番目の Product の c 番目の係数を返します。ただし、100 程度を超える大きな製品の場合は、やはり非常に遅くなります。これを実行すると、再帰が明らかに答えではないことがわかります。

unsigned int numbertheory::mahonian(unsigned int r, unsigned int c)
  {
      unsigned int result=0;
      unsigned int k;

     if(r==0 && c==0)
       return 1;
     if( r==0 && c!=0)
      return 0;

   for(k=0; k <= r; k++)
       if(r > 0 && c >=k)
           result = result + mahonian(r-1,c-k);

   return result;

}

興味深いことに、再帰の例よりもはるかに高速な Sashank の c++ バージョンである以下を含めました。アルマジロライブラリを使用していることに注意してください。

uvec numbertheory::mahonian_row(uword n){
 uword i = 2;
 uvec current;
 current.ones(i);
 uword current_size;
 uvec prev;
 uword prev_size;

 if(n==0){
   current.ones(1);
   return current;
 }

 while (i <= n){                  // increment through the rows
   prev_size=current.size();     // reset prev size to current size
   prev.set_size(prev_size);     // set size of prev vector
   prev= current;                //copy contents of current to prev vector
   current_size =1+ (i*(i+1)/2);      // reset current_size
   current.zeros(current_size);    // reset current vector with zeros

   for(uword j=0;j<i+1; j++)       //increment through current vector
      for(uword k=0; k < prev_size;k++)
         current(k+j) += prev(k);
   i++;                                        //increment to next row
}
return current;                                //return current vector
 }

 uword numbertheory::mahonian_fast(uword n, uword c) {
**This function returns the coefficient of c order of row n of
**the Mahonian numbers
    // check for input errors
    if(c >= 1+ (n*(n+1)/2)) {
        cout << "Error. Invalid input parameters" << endl;
   }
   uvec mahonian;
   mahonian.zeros(1+ (n*(n+1)/2));
   mahonian = mahonian_row(n);
   return mahonian(c);
 }
于 2017-08-31T23:28:52.110 に答える