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

}

What is your problem exactly? Do you get an incorrect output? If yes, what do you get and what do you expect to? — kraskevich
– kraskevich, Commented Dec 29, 2016 at 21:23

Adrian Colomitchi · Accepted Answer · 2016-12-30 00:19:27Z

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]

kraskevich · Accepted Answer · 2016-12-29 21:35:40Z

0

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

answered Dec 29, 2016 at 21:35

kraskevich

18.6k4 gold badges37 silver badges46 bronze badges

4 Comments

wayfare Over a year ago

made suggested changes but I think I am not getting desired output. Input: char[] arr = {'a','b','c','d'}; int[] p = {2,0,1,3}; and output is [c, a, b, d] Also it would be very helpful if you can explain why is this change needed.

kraskevich Over a year ago

@wayfare [c, a, b, d] looks correct to me. You don't need the last swap as you shift the entire cycle without it.

wayfare Over a year ago

Shouldn't output be {b,c,a,d} instead of [c, a, b, d] ? Because p = {2,0,1,3} and so a goes to third position instead of second. (starting index from 0)

kraskevich Over a year ago

@wayfare Actually, it's a matter of interpretation. I read it like: a[p[0]] becomes the first element, a[p[1]] goes after it and so on.

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related