arrays - 定数空間で配列をインターリーブする

Question

配列 a1、a2、...、an、b1、b2、...、bn があるとします。

目標は、この配列を O(n) 時間と O(1) 空間で a1、b1、a2、b2、...、an、bn に変更することです。言い換えれば、一定量以上の追加ストレージを使用せずに、配列をその場で変更するための線形時間アルゴリズムが必要です。

これはどのように行うことができますか？

Answer 1

これは私がペンと紙で作ったシーケンスとメモです。それ、またはバリエーションは、より大きなnにも当てはまると思います。

各行は異なるステップを表し、（）はこのステップで移動されているものを示し、[]は最後のステップから移動されたものを示します。配列自体はストレージとして使用され、次に何を移動するかを決定するために2つのポインター（1つはL用、もう1つはN用）が必要です。Lは「文字の線」、Nは「数直線」（移動するもの）を意味します。

   ABCD 1 2 3 4

LABC（D）1 2 3 4最初はL、最後のNを移動する必要はありません
NABC（3）1 2 [D] 4
LAB（C）2 1 [3] D 4
NAB 1（2）[C] 3 D 4
LA（B）1 [2] C 3 D 4
NA（1）[B] 2 C 3 D 4
   A [1] B 2 C 3 D 4完了、移動する必要はありませんA

さまざまな「ポインタジャンプ」に注意してください。Lポインタは常に1ずつ減少しますが（それより速く食べることはできないため）、Nポインタは「それ自体を置き換えた」（スポットで2つ下にジャンプ）かどうかに応じてジャンプします。何かを交換した場合（ジャンプしないので、次の何かがうまくいく可能性があります！）。

Answer 2

この問題は見かけほど簡単ではありませんが、少し考えてみると、これを達成するためのアルゴリズムはそれほど悪くありません。最初と最後の要素は既に配置されているので、気にする必要はありません。変更が必要な配列の前半の最初の項目を表す左インデックス変数を保持します。その後、右側のインデックス変数を、変更が必要な配列の後半の最初の項目に設定します。ここで行うことは、左側のインデックス アイテムに到達するまで、右側のインデックスのアイテムを 1 つずつ下にスワップするだけです。左のインデックスを 2 ずつ、右のインデックスを 1 ずつ増やし、インデックスが重複するか、左のインデックスが右のインデックスを超えるまで繰り返します (右のインデックスは常に配列の最後のインデックスで終了します)。

疑似コード

1. 左のインデックスを 1 に設定
2. 右インデックスを中央に設定 (配列の長さ / 2)
3. 左インデックスの項目が置換されるまで、右インデックスの項目をその直前の項目と交換します
4. 左のインデックスを 2 増やします
5. 右側のインデックスを 1 増やします
6. 左のインデックスが右のインデックス以上になるまで、3 ～ 5 を繰り返します。

C(#) のインターリーブ アルゴリズム

protected void Interleave(int[] arr)  
{  
    int left = 1;  
    int right = arr.Length / 2;  
    int temp;  

    while (left < right)  
    {  
        for (int i = right; i > left; i--)  
        {  
            temp = arr[i];  
            arr[i] = arr[i - 1];  
            arr[i - 1] = temp;  
        }  

        left += 2;  
        right += 1;  
    }  
}    

このアルゴリズムは、O(1) ストレージを使用します (temp 変数を使用します。これは、加算/減算スワップ手法を使用して削除できます)。実行時分析はあまり得意ではありませんが、多くのスワップを再実行します。おそらく、誰かがランタイム分析をさらに調査できるでしょう。

Answer 3

これはインプレース イン シャッフル問題と呼ばれます。hereに基づいた C++ での実装を次に示します。

void in_place_in_shuffle(int arr[], int length)
{
    assert(arr && length>0 && !(length&1));

    // shuffle to {5, 0, 6, 1, 7, 2, 8, 3, 9, 4}
    int i,startPos=0;
    while(startPos<length)
    {
        i=_LookUp(length-startPos);
        _ShiftN(&arr[startPos+(i-1)/2],(length-startPos)/2,(i-1)/2);
        _PerfectShuffle(&arr[startPos],i-1);
        startPos+=(i-1);
    }

    // local swap to {0, 5, 1, 6, 2, 7, 3, 8, 4, 9}
    for (int i=0; i<length; i+=2)
        swap(arr[i], arr[i+1]);
}

// cycle
void _Cycle(int Data[],int Lenth,int Start)
{
    int Cur_index,Temp1,Temp2;

    Cur_index=(Start*2)%(Lenth+1);
    Temp1=Data[Cur_index-1];
    Data[Cur_index-1]=Data[Start-1];

    while(Cur_index!=Start)
    {
        Temp2=Data[(Cur_index*2)%(Lenth+1)-1];
        Data[(Cur_index*2)%(Lenth+1)-1]=Temp1;
        Temp1=Temp2;
        Cur_index=(Cur_index*2)%(Lenth+1);
    }
}


// loop-move array
void _Reverse(int Data[],int Len)
{
    int i,Temp;
    for(i=0;i<Len/2;i++)
    {
        Temp=Data[i];
        Data[i]=Data[Len-i-1];
        Data[Len-i-1]=Temp;
    }
}

void _ShiftN(int Data[],int Len,int N)
{
    _Reverse(Data,Len-N);
    _Reverse(&Data[Len-N],N);
    _Reverse(Data,Len);

}

// perfect shuffle of satisfying [Lenth=3^k-1] 
void _PerfectShuffle(int Data[],int Lenth)
{
    int i=1;

    if(Lenth==2)
    {
        i=Data[Lenth-1];
        Data[Lenth-1]=Data[Lenth-2];
        Data[Lenth-2]=i;
        return;
    }
    while(i<Lenth)
    {
        _Cycle(Data,Lenth,i);
        i=i*3;
    }
}

// look for 3^k that nearnest to N
int _LookUp(int N)
{
    int i=3;
    while(i<=N+1) i*=3;

    if(i>3) i=i/3;

    return i;
}

---

テスト：

int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};  
int length = sizeof(arr)/sizeof(int);
in_place_in_shuffle(arr, length);

この後、 にarr[]なります{0, 5, 1, 6, 2, 7, 3, 8, 4, 9}。

Answer 4

まず、理論: 「順列サイクル」で要素を再配置します。要素を取得して新しい位置に配置し、現在そこにある要素を置き換えます。次に、その移動した要素を新しい位置に配置します。これにより、さらに別の要素が置換されるため、すすぎと繰り返しを繰り返します。移動した要素が、最初に開始した要素の位置に属している場合、1 つのサイクルが完了しています。

実際、あなたの質問は私がここで尋ねた質問の特殊なケースです。つまり、O(N) 時間と O(1) 空間で配列を任意の順序に再配置するにはどうすればよいですか? 私の質問では、再配置された位置は数値の配列で記述されます。n 番目の位置の数値は、元の配列内の要素のインデックスを指定します。

ただし、問題にはこの追加の配列がなく、割り当てには O(N) スペースが必要です。幸いなことに、次のように、この配列内の任意の要素の値をオンザフライで計算できます。

int rearrange_pos(int x) {
    if (x % 2 == 0) return x / 2;
    else return (x - 1) / 2 + n; // where n is half the size of the total array
}

ここでは、再配置アルゴリズム自体を複製しません。私の質問に対する受け入れられた回答で見つけることができます。

編集:ジェイソンが指摘したように、私がリンクした回答では、bool の配列を割り当てて、O(N) スペースにする必要があります。これは、順列が複数のサイクルで構成される可能性があるためです。私はあなたの特別なケースのためにこの配列の必要性を排除しようとしましたが、成功しませんでした..使用可能なパターンはないようです. たぶん、他の誰かがここであなたを助けることができます.

Answer 5

最初に配列をリンクリストに変換できれば、問題は簡単になります。