0

任意の数のポイントを取得できる配列があり、ポイントにはインデックスが付けられます。

次に、すべての順列を作成する非再帰的なソリューションを実行しています

それは実行され、これ1,2,3,4,5,6,7,8,9,0で終了し0,9,8,7,6,5,4,3,2,1 ます。時間の複雑さがあります

ここで、これらの順列の中間点を見つけて、パターンを最初からスレッドで実行し、時間の複雑さを軽減できるようにしたいと思います。

どうすれば中間点を見つけることができますか?

Java の場合:

    public Path QuickPerm(int[] points) {
       int N = points.length;
       int a[] = points ;
       int p[] = new int[N];
       Path shortest = null;
       Path current = null;
       int i;
       int j;
       int tmp; // Upper Index i; Lower Index j
       for(int i1 = 0; i1 < N; i1++) {  
          p[i1] = 0;       // p[i] == i controls iteration and index boundaries for i
       }
       //display(a, 0, 0);   // remove comment to display array a[]
       i = 1;   // setup first swap points to be 1 and 0 respectively (i & j)
       while(i < N) {
          if (p[i] < i) {
             j = i % 2 * p[i];   // IF i is odd then j = p[i] otherwise j = 0
             tmp = a[j];         // swap(a[j], a[i])
             a[j] = a[i];
             a[i] = tmp;
                                 //save 
             p[i]++;             // increase index "weight" for i by one
             i = 1;              // reset index i to 1 (assumed)
          } else {               // otherwise p[i] == i
             p[i] = 0;           // reset p[i] to zero
             i++;                // set new index value for i (increase by one)
          } // if (p[i] < i)
       }
       return shortest;// while(i < N)
    } // QuickPerm()
4

2 に答える 2

1

http://en.wikipedia.org/wiki/Lehmer_codeでは、順列に番号を付ける方法の 1 つについて説明しています。これにより、たとえば途中で番号を取得して、それがどの順列であるかを調べることができます。

スレッドの内容によっては、すべての順列に同じ時間がかかるとは限らないため、順列のリストを途中で分割すると、作業のバランスが正確に取れません。人々がこれを処理した 1 つの方法は、作業を多数の小さな断片に分割し、何もすることがないときはいつでもスレッドに小さな作業を選択させることです。次に、一部の作業が他の作業よりも長くかかったとしても、それほど問題ではありません。それらの作業でスタックしたスレッドは、単純に少数の作業を行うことになりますが、ほとんど同じ時間がかかります。

于 2013-10-05T18:56:36.857 に答える
0

lexico-order を使用する次の順列アルゴリズムを使用すると、これは簡単になります。たとえば、wikipedia を参照してください :

(n のいくつかの値について中央のインデックスを確認すると、パターンがすぐにわかります。たとえば、1234 の場合、インデックスがゼロのシーケンスの要素 12 は 1243 になり、12345 の場合、要素 60 は 12354 になります。)

于 2013-10-05T17:51:37.820 に答える