ベクトルの順列

Question

私はベクトルを持っていると仮定します：

 0  1  2  3  4  5
[45,89,22,31,23,76]

とそのインデックスの順列ます：

[5,3,2,1,0,4]

これ順列に応じて取得することを訴えるための効率的な方法はあります：

[76,31,22,89,45,23]

ほとんどのO（1）追加のスペースで使用しているか？

Answer 1

はい。左端の位置から始まって、私たちは、私がその位置iにおける（その他）見当違いの要素とそれを交換することによって、その正しいの位置の中にあり、の要素を置きます。我々はO（1）追加のスペースを必要とするところです。私たちは、この位置にある要素が正しくなるまで周りの要素のペアを交換しておきます。だけにして、我々は次の位置に進み、同じことを行うのです。

の例：の

[5 3 2 1 0 4]初期状態

[4 3 2 1 0 5]スワップ（5,4）、5が正しい位置にあるが、図4は、まだ間違っている

[0 3 2 1 4 5]（4,0）スワップ、今4と0の両方が正しい位置にある、

次の位置に移動

[0 1 2 3 4 5]次に、（3,1）スワップ1及び3は、次の位置に移動し、正しい位置に両方とも

[0 1 2 3 4 5]の全ての要素が正しい位置にある、端

注

各スワップ操作が正しい位置にある要素（2つのうちの）少なくとも一つを置くので、

、我々は完全にNそのようなスワップよりも多くを必要としない。

Answer 2

ザックのソリューションは非常に良いです。

並べ替えする必要がある理由は、

それでも、私は思っていました。あなたはインデックスの順列を持っている場合は、古い配列へのポインタとしての値を使用します。

これは最初の場所で配列をソートする必要性を排除することができます。これは、すべての場合に使用することができます解決策はありませんが、それはほとんどの場合、正常に動作します。

例

a = [45,89,22,31,23,76];
b = [5,3,2,1,0,4]

あなたが の中の値を通じてLOPしたい場合は、

さて、あなたは（擬似コード）のような何かを行うことができます：

for i=0 to 4
{
    process(a[i]);
}

あなたが新しい順に値をループにしたい場合は、実行します：

for i=0 to 4
{
    process(a[b[i]]);
}

先に述べたように、

、このsoluionは多くの場合十分かもしれないが、かもしれない他のいくつかの例インチ何のソートは全く必要ありませんので、あなたは、このソリューションを使用することができますケースのためZach.Butによるソリューションを使用することができ、他のケースでは、それが優れてます。