Permute I 및 T [i

Question

int t의 배열이 있다고 가정하면 I 및 T [i]를 퍼 뜨리는 내내 알고리즘을 찾고 있습니다.

나는 : [3 2 0 1] (a)

나는 원한다 : [2 3 1 0] (b)

예를 들어. (b)에서 t [0] = 2에서 (a) t [2]에서 0과 같기 때문입니다.

간단한 O (N) 시간, O (1) 우주 알고리즘을 찾을 것으로 기대했지만 찾을 수 없습니다. 어떤 아이디어?

메모 :

• SIGLE ARRAY (a)는 (B)가 이후에 하나가 있습니다.

• 배열의 값은 [0, n [, 중복 없음에 속합니다.

Answer 1

순열의 역전을 얻으려면 순열의주기를 걸어야합니다.

int i, j, next, prev;
for(int i=0; i<N; i++) {
  if(T[i]>=N) continue;
  j=T[i];
  prev=i;
  while(j < N) {
    next=T[j];
    T[j]=prev+N;
    prev=j;
    j=next;
  }
}
for(int i=0; i<N; i++)
  T[i]-=N;

나는 N보다 큰 숫자를 사용하여 이미 처리 된 사이클의 일부입니다.

Answer 2

가능한 모든 순열을 얻기 위해 사전 주문을받을 수 있습니다. 순열 알고리즘 목록은 아래 링크를 따르십시오.

순열

Answer 3

당신은 당신이 순열 그룹 배열의. 예제 배열은 {0 → 3, 1 → 2, 2 → 0, 3 → 1}이며 {3 → 0, 2 → 1, 0 → 2, 1 → 3}을 원합니다. 재 배열, 그것은 {0 → 2, 1 → 3, 2 → 1, 3 → 0} 또는 [2 3 1 0]입니다. 따라서 역전을 찾으려면 원래 배열을 반복하고 인덱스 매핑을 뒤집어야합니다. 이것은 작동해야합니다 (길이를 알고있는 경우 모든 배열을 사용할 수 있음) :

int t[] = { 3, 2, 0, 1};
int tinv[4];
for (int i = 0; i < 4; i++)
    tinv[t[i]] = i;

t (길이 n을 가진)가 [0 .. n-1]의 순열 인 한, Tinv는 값에 대해 정의되지 않아야합니다. Jpalecek의 솔루션은 다소 복잡하기 때문에 이것이 당신에게 충분히 포괄적인지 확실하지 않습니다.

Answer 4

이것은 여분의 기억 없이이 문제를 해결하려는 나의 시도입니다. O (N) 알고리즘입니다.

JPalecek의 알고리즘은 매우 지능적이지만 적어도 나에게는 읽기에 직관적이지 않습니다. 나는 그것을 시도했고 그것은 작동하지만 왜 그런지, 의견이 위대한 이유를 이해할 시간이 없었습니다.

Gracenotes의 알고리즘은 배열이 너무 크지 않는 한 훌륭합니다. 데이터가 크면 배열을 동적으로 만들어야 할 수도 있습니다.

내 알고리즘의 기본 아이디어는 색인 및 값 쌍의 체인을 따라 배열을 업데이트하는 것입니다. 예를 들어 index 0은 값으로 맵핑 3 값 3으로 값 3을 사용하여 배열 및 값에서 인덱스 3 인 다음 쌍을 찾을 수 있습니다. 기본적으로 다음 인덱스와 값 쌍을 저장하고 이전 인덱스 및 쌍 값을 업데이트합니다. 내가 체인을 끝날 때까지.

더 효율적이고 우아하거나 전반적으로 더 잘 만들 수 있다면 관심이 있습니다.

아래 코드를 컴파일하고 테스트했지만 다른 테스트 입력을 사용하지 않았습니다. 나는 그것을 시도하고 그것이 어떻게 작동하는지 더 잘 이해하려는 사람들을 위해 디버그 출력을 남겼습니다.

// Array print routine.
void printArray (const char * str_p,int a[], int n)
{
   printf ("%s\n", str_p);
   for (int i = 0; i < n; i++)
   {
      printf ("%i ", i);
   }
   printf ("\n");
   for (int i = 0; i < n; i++)
   {
      printf ("%i ", a[i]);
   }
   printf ("\n\n");
}

// The main code.
void PermuteTheDamnArray()
{
   printArray ("Initial Array", a,n);

   int i = 0;     // Simply a counter.
   int p_ix = 0;  // Previous Index.
   int p_val = a[0]; // Previous Value.
   int n_ix = a[0];  // Next index.
   int n_val = a[n_ix]; // Next Value.
   for (i = 0; i < n; i++)
   {
      // Replace. 
      printf ("Swapping orig (%i,%i) with (%i,%i)\n", n_ix, n_val,p_val, p_ix);
      a[p_val] = p_ix;

      printArray ("Array after swap", a,n);

      // The next index and value pair becomes the new previous index and value pair.
      p_ix = n_ix;
      p_val = n_val;
      printf ("The previous pair is now: (%i,%i)\n", p_ix, p_val);

      // Get the next index and value pair.
      n_ix = n_val;
      n_val = a[n_val];
      printf ("The next pair is now: (%i,%i)\n", n_ix, n_val);

   }

   printArray ("Final Array", a,n);
}



Output:

Swapping orig (3,1) with (3,0)
Array after swap
0 1 2 3 
3 2 0 0 

The previous pair is now: (3,1)
The next pair is now: (1,2)
Swapping orig (1,2) with (1,3)
Array after swap
0 1 2 3 
3 3 0 0 

The previous pair is now: (1,2)
The next pair is now: (2,0)
Swapping orig (2,0) with (2,1)
Array after swap
0 1 2 3 
3 3 1 0 

The previous pair is now: (2,0)
The next pair is now: (0,3)
Swapping orig (0,3) with (0,2)
Array after swap
0 1 2 3 
2 3 1 0 

The previous pair is now: (0,3)
The next pair is now: (3,0)
Final Array
0 1 2 3 
2 3 1 0