0

I have and array that can take any number of points, and the points are given an index.

Then I am running a non recursive solution that creates all permutations

It runs through 1,2,3,4,5,6,7,8,9,0 and ends with 0,9,8,7,6,5,4,3,2,1 this has a time complexity to it

Now, I would like to find the middle point of these permutations so that I can run the pattern from the start and the middle with threads to reduce the time complexity.

How would I find the middle point?.

In 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描述了一种对排列进行编号的方法，以便您可以决定例如取一个数字中途并找出它是什么排列。

根据您的线程所做的事情，您可能会发现并非所有排列都花费相同的时间，因此将排列列表分成一半并不能完全平衡工作。人们处理这个问题的一种方法是将工作分成大量的小块，让你的线程在它们无事可做的任何时候挑选一小块工作。然后，如果某些工作比其他工作花费更长的时间，那就没关系了 - 被它们卡住的线程最终只会在较少数量的工作上工作，但花费的时间几乎相同。

于 2013-10-05T18:56:36.857 回答
0

使用使用 lexico-order 的 next-permutation 算法将使这变得轻而易举，例如参见 wikipedia： http ://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

（检查中间索引中的几个 n 值，您会立即看到模式，例如对于 1234，零索引序列中的元素 12 将是 1243，对于 12345，元素 60 将是 12354。）

于 2013-10-05T17:51:37.820 回答