iとT [i]を並べ替える

Question

int Tの配列があると仮定すると、 iとT [i]

を入れ替えるインプレースアルゴリズムを探しています。

持っている：[3 2 0 1]（a）

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

eg。 （b）T [0] = 2の理由は、（a）T [2]が0に等しいからです。

単純なO（n）時間、O（1）空間アルゴリズムを見つけることを期待していましたが、見つけることができません。どんなアイデア？

注：

• 1つのシグル配列があります（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＆＃8594; 3、1＆＃8594; 2、2＆＃8594; 0、3＆＃8594; 1}であり、{3＆＃8594; 0、2＆＃8594; 1、0＆＃8594; 2、1＆＃8594; 3}。再配置すると、{0＆＃8594; 2、1＆＃8594; 3、2＆＃8594; 1、3＆＃8594; 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のアルゴリズムは優れています。データが大きい場合、配列を動的に作成する必要があります。

私のアルゴリズムの基本的な考え方は、インデックスと値のペアのチェーンをたどって配列を更新することです。たとえば、インデックス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