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

Question

I been trying to implement what been discussed here in this thread Algorithm to apply permutation in constant memory space. However I am not able to may be understand the problem solution correctly or my code has some bug which I cant detect and fix. Ant kind of help is appreciated.

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

Don't use the very array elements to keep the displaced values (i.e. swap between the elements of the initial array), this is how you screwed your code.

Instead, use some O(1) temp variables to keep the "displaced" value and where from that value originated.

Commented code below, with 2 test cases (note the use of Arrays.toString instead of your custom print(char[]/int[]) methods)

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));
  }

}

Output:

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]

Answer 2

You don't need to make a swap when your reach the beginning of the cycle. That is, it should go like:

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;
}