작동하도록 배열의 순열을 구현할 수 없습니다.

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

: 즉,이 같이 가야한다.

대신 O "(1) 임시 변수를 사용하여"배치 된 "값과 그 값의 원래 위치를 유지하십시오.

2 테스트 케이스 (print(char[]/int[]) 방법 대신 사용자의 Arrays.toString의 사용에주의)로, 아래의 코드를 댓글

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] 

Answer 2

당신은 스왑을 할 필요가 없습니다 때 당신의 손이 닿지주기의 시작입니다. 이것은 당신이 당신의 코드를 나사 방법입니다 (초기 배열의 요소들 사이 즉 스왑) 변위 값을 유지하기 위해 매우 배열 요소를 사용하지 마십시오

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