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