並び替える私が持っている私はint型T、 の配列を持っていることを、私は私とTを入れ替えin-placeアルゴリズムを探していますと仮定すると、iとT [i]を

Question

[i]は

：[3 2 0 1 ]（a）は

私が欲しい：[2 3 1 0]（b）は

など。 O（n）time、O（1）spaceアルゴリズムを見つけることを期待していましたが、T（0）= 2でT（0）= 2でした。私はそれを見つけることができません。何か案は ？

注：

• の（a）（b）の後で前にある1つのSIGLE配列があります。

• 配列内の値は[0、N [重複しません。

Answer 1

順列の反転を得るために、あなたはちょうど私がこれをマークするために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; 

を歩かなければならすでに処理されたサイクルの一部であります。

Answer 2

可能なすべての並べ替えを取得するために、辞書順に進むことができます。

Permutations

Answer 3

あなたが、配列のpermutation groupで逆を探しているようだ順列アルゴリズムのリストについては、以下のリンクに従ってください。あなたの例の配列は{0→3,1→2,2→0,3→1}で、{3→0,2→1→0→2,1→3}となります。 Rearranged、それは{0→2,1→3,2→1,3→0}、または[2 3 1 0]です。したがって、逆行列を見つけるには、元の配列を繰り返し処理し、インデックスのマッピングを逆にするだけです。順列である（長さnの）T限り

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

を[0 ... N-1]、TINVはすべきではない：これは（あなたは長さを知っている場合は、任意の配列を使用することができます）動作するはずです任意の値に対して未定義です。 jpalecekの解決策は多少複雑ですので、十分に包括的かどうかはわかりません。

Answer 4

これは、余分なメモリなしで、この問題をその場で解決しようとしています。これはO（n）アルゴリズムです。

jpalecekによるアルゴリズムは、少なくとも知的ではありますが、少なくとも私にとっては読解するのに直感的ではありません。私はそれを試して、それは動作しますが、私は理由とコメントが素晴らしいだろうと理解する時間がなかった。

配列が大きすぎない限り、Gracenotesによるアルゴリズムは素晴らしいです。データが大きい場合は、アレイを動的に作成する必要があります。

私のアルゴリズムの基本的な考え方は、インデックスと値のペアの連鎖に従って配列を更新することです。たとえば、インデックス0は値3にマッピングされます。インデックスとして値3を使用すると、配列内のインデックス3と値1の次のペアが見つけられます。基本的に次のインデックスと値のペアを保存し、前のインデックスとペア値私がチェーンをやるまで。

もっと効率的に、エレガントに、全体的にもっと良くすることができれば、私は興味があります。

以下のコードをコンパイルしてテストしましたが、他のテスト入力は使用していません。私はそれを試して、それがどのように動作するかをよりよく理解したい人のために、デバッグ出力に残しました。

// 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