无法实现数组的就地排列工作

Question

我一直在尝试实现在此线程中讨论的内容 Algorithm to apply permutation in constant memory space。但是我无法正确理解问题的解决方案，或者我的代码有一些我无法检测和修复的错误。蚂蚁类的帮助表示赞赏。

public class ArrayPermute{

    public static void main(String[] args){
            char[] arr =  {'a','b','c','d'};
            int[] p = {2,0,1,3};

            for(int i=0; i<arr.length; i++){
                    int tmp = i;
                    while(p[tmp] >= 0){
                            char t = arr[p[tmp]];//d
                            arr[p[tmp]] = arr[tmp];
                            arr[tmp]=t;
                            int _tmp = p[tmp];
                            p[tmp] = -1;
                            tmp = _tmp;
                            print(arr);
                            print(p);
                    }
            }

            for(char i: arr){
                    System.out.print(i + " ");
            }

    }

    public static void print(char[] arr){
            for(char c: arr){
                    System.out.print(c + " " );
            }
            System.out.println();
    }

    public static void print(int[] arr){
            for(int c: arr){
                    System.out.print(c + " " );
            }
            System.out.println();
    }

}

Answer 1

到达周期开始时，您无需进行交换。也就是说，它应该是这样的：

int tmp = i;
int start = i;
while (p[tmp] >= 0 && p[tmp] != start) {
    // Your code here doesn't change
}
if (p[tmp] == start) {
    p[tmp] = -1;
}

Answer 2

不要使用数组元素来保留置换后的值（即在初始数组的元素之间交换），这就是你搞砸代码的方式。

相反，使用一些 O(1) 临时变量来保留 "displaced" 值以及该值的来源。

下面的注释代码，有 2 个测试用例（注意使用 Arrays.toString 而不是您自定义的 print(char[]/int[]) 方法）

import java.util.Arrays;

public class InPlacePermutation {

  static public void inPlacePermute(char arr[], int p[]) {
    for(int i=0; i<p.length; i++) {
      if(p[i]<0) continue; // already visited

      char toMove=arr[i]; // value-at-hand
      int currIx=i;       // index from where the value-at-hand originated

      while(currIx>=0 && p[currIx]!=i) { // as long as we aren't back where we started
        int destIx=p[currIx];
        if(destIx<0) { 
          // the permutation is bad, we are stepping again
          // on places we stepped before. This should not happen
          throw new IllegalArgumentException("bad permutation");
        }
        // take the value "at hand" before it get overwritten
        char destVal=arr[destIx];
        // place current "value at hand" in the destination
        arr[destIx]=toMove;

        // update bookkeeping the vals/indexes values
        p[currIx]=-1; // mark where we've been

        currIx=destIx; // then take a step further
        toMove=destVal; // don't forget to carry the new "value at hand" 
      }
      // now we are back where we started with a "value at hand"
      arr[i]=toMove;
      p[currIx]=-1; // mark the source of the moved value as visited
    }
  }

  static public void main(String[] args) {
    char[] arr =  {'a','b','c','d'};
    int[] p = {2,0,1,3};

    System.out.print("arr:"+Arrays.toString(arr)+" + pmt:"+Arrays.toString(p) + " =>");
    inPlacePermute(arr, p);
    System.out.println("  "+Arrays.toString(arr));
    System.out.println();

    // two cycles and one in place
    arr =  new char[]{'a','b','c','d', 'e', 'f'};
    p = new int[]{2,3,4,1,0,5};
    System.out.print("arr:"+Arrays.toString(arr)+" + pmt:"+Arrays.toString(p) + " =>");
    inPlacePermute(arr, p);
    System.out.println("  "+Arrays.toString(arr));
  }

}

输出：

arr:[a, b, c, d] + pmt:[2, 0, 1, 3] =>  [b, c, a, d]

arr:[a, b, c, d, e, f] + pmt:[2, 3, 4, 1, 0, 5] =>  [e, d, a, b, c, f]

无法实现数组的就地排列工作

Can't get implementation of in place permutation of array to work

arrays

algorithm

permutation

in-place

best-in-place