문제
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 [, 중복 없음에 속합니다.
해결책
순열의 역전을 얻으려면 순열의주기를 걸어야합니다.
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보다 큰 숫자를 사용하여 이미 처리 된 사이클의 일부입니다.
다른 팁
가능한 모든 순열을 얻기 위해 사전 주문을받을 수 있습니다. 순열 알고리즘 목록은 아래 링크를 따르십시오.
당신은 당신이 순열 그룹 배열의. 예제 배열은 {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의 솔루션은 다소 복잡하기 때문에 이것이 당신에게 충분히 포괄적인지 확실하지 않습니다.
이것은 여분의 기억 없이이 문제를 해결하려는 나의 시도입니다. 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