11

偶数サイズの文字列が与えられた場合、次のように言います。

abcdef123456

同じ文字列が次のようになるように、2 つの半分をどのようにインターリーブしますか。

a1b2c3d4e5f6

アルゴリズムを開発しようとしましたが、できませんでした。どのように進めるかについて、誰かが私にいくつかのヒントを教えてくれますか? 余分な文字列変数や配列を作成せずにこれを行う必要があります。1 つまたは 2 つの変数で問題ありません。

動作するコード (またはアルゴリズム) が必要ないだけです。アルゴリズムを開発し、その正確性を数学的に証明する必要があります。

4

6 に答える 6

3

一般的に、この問題は非常に難しく、置換サイクルを見つけることになります。それらの数と長さは、長さによってかなり異なります。

10 および 12 エントリ配列のインプレース インターリーブのサイクル

最初と最後のサイクルは常に縮退します。10 エントリの配列には長さ 6 と 2 の 2 つのサイクルがあり、12 エントリの配列には長さ 10 の 1 つのサイクルがあります。

サイクルを使用すると、次のことが行われます。 

 for (i=j; next=get_next(i) != j; i=next) swap(i,next);

関数 next は N の比較的簡単な式として実装できますが、どのインデックスが交換されたかを簿記するために問題は延期されます。左の 10 エントリのケースでは、[すばやく] サイクルの開始位置を見つける必要があります (たとえば、1 と 3 です)。

于 2013-04-14T07:10:00.977 に答える
2

解決策はこちら J. Ellis と M. Markov です。完全なシャフデによるその場での安定したマージ。コンピュータジャーナル。43(1):40-53、(2000)。

ここでのさまざまな議論も参照してください。

  1. https://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array/400#400
  2. https://cstheory.stackexchange.com/questions/13943/linear-time-in-place-riffle-shuffle-algorithm .
于 2013-04-14T07:01:04.893 に答える
2

わかりました、最初からやり直しましょう。ここで行うことは次のとおりです。

def interleave(string):
    i = (len(string)/2) - 1
    j = i+1

    while(i > 0):
        k = i
        while(k < j):
            tmp = string[k]
            string[k] = string[k+1]
            string[k+1] = tmp
            k+=2 #increment by 2 since were swapping every OTHER character
        i-=1 #move lower bound by one
        j+=1 #move upper bound by one

これは、プログラムが実行しようとしているものの例です。変数i、j、を使用しますk。iそしてjはそれぞれ下限と上限kになり、 は交換するインデックスになります。

例

`abcd1234`

i = 3 //got this from (length(string)/2) -1

j = 4 //this is really i+1 to begin with

k = 3 //k always starts off reset to whatever i is 

swap d and 1
increment k by 2 (k = 3 + 2 = 5), since k > j we stop swapping

result `abc1d234` after the first swap

i = 3 - 1 //decrement i
j = 4 + 1 //increment j
k= 2 //reset k to i

swap c and 1, increment k (k = 2 + 2 = 4), we can swap again since k < j
swap d and 2, increment k (k = 4 + 2 = 6), k > j so we stop
//notice at EACH SWAP, the swap is occurring at index `k` and `k+1`

result `ab1c2d34`

i = 2 - 1
j = 5 + 1
k = 1

swap b and 1, increment k (k = 1 + 2 = 3), k < j so continue
swap c and 2, increment k (k = 3 + 2 = 5), k < j so continue
swap d and 3, increment k (k = 5 + 2 = 7), k > j so were done

result `a1b2c3d4`

プログラムの正しさの証明については、このリンクを参照してください。ループ不変条件を使用して、これが正しいことを証明する方法を説明します。

大まかな証明は次のようになります。

  1. i初期化: ループの最初の反復の前に、が に設定されて いることがわかります(length(string)/2) - 1。ループに入る前に、 i <= length(string) であることがわかります。
  2. メンテナンス。各反復の後、iはデクリメントされ ( i = i-1, i=i-2,...)、その時点で が存在する必要がありますi<length(string)。
  3. 終了:iは正の整数の減少するシーケンスであるため、ループの不変式i > 0は最終的に false と等しくなり、ループは終了します。
于 2013-04-14T06:17:48.703 に答える
0

よし、これがラフ案だ。アルゴリズムが欲しいだけではなく、ヒントを取っていると言うので、このアルゴリズムをヒントと考えてください。

長さはNです。

k = N/2 - 1。

1) 中央から開始し、位置 N/2 k の位置にある要素を (隣接するペア要素を連続的に交換することによって) 左にシフトします (1 回目: '1' は位置 1 に移動します)。

2) --k. k==0 ですか? 終了する。

3) 要素を N/2 (1 回目: 'f' は N-1 の位置に移動) k 桁右に移動します (交換により)。

4) --k.

編集：以下のコードが示すように、上記のアルゴリズムは正しいです。実際にそれが正しいことを証明することは、私の能力を超えていますが、楽しい小さな質問です.

#include <iostream>
#include <algorithm>

int main(void)
{
    std::string s("abcdefghij1234567890");
    int N = s.size();
    int k = N/2 - 1;
    while (true)
    {

        for (int j=0; j<k; ++j)
        {
            int i = N/2 - j;
            std::swap(s[i], s[i-1]);
        }

        --k;

        if (k==0) break;

        for (int j=0; j<k; ++j)
        {
            int i = N/2 + j;
            std::swap(s[i], s[i+1]);
        }

        --k;
    }

   std::cout << s << std::endl;

   return 0;
}
于 2013-04-14T07:07:36.150 に答える