7

質問を書き直したので、熱心な編集者によるさらなる速攻の回答や時期尚早の閉鎖に苦しむ前に、これはこの質問の複製ではないことを指摘させてください。配列から重複を削除する方法を知っています。

この質問は、厳密な意味での重複ではなく、配列からシーケンスを削除することに関するものです。

配列内の要素の次のシーケンスを考えてみましょう。

[0] a
[1] a
[2] b
[3] c
[4] c
[5] a
[6] c
[7] d
[8] c
[9] d

この例では、次のものを取得したい...

[0] a
[1] b
[2] c
[3] a
[4] c
[5] d

重複する要素は保持されますが、同じ要素のシーケンスはその要素の 1 つのインスタンスに縮小されていることに注意してください。

さらに、2 つの行が繰り返される場合は、1 つのセット (2 つの行の) に減らす必要があることに注意してください。

[0] c
[1] d
[2] c
[3] d

...に還元...

[0] c
[1] d

私は C# でコーディングしていますが、任意の言語のアルゴリズムを高く評価しています。

4

4 に答える 4

3

編集：いくつかの変更と新しい提案を行いました

スライディングウィンドウはどうですか...

REMOVE LENGTH 2: (no other length has other matches)
//the lower case letters are the matches
ABCBAbabaBBCbcbcbVbvBCbcbcAB  
__ABCBABABABBCBCBCBVBVBCBCBCAB

REMOVE LENGTH 1 (duplicate characters):
//* denote that a string was removed to prevent continual contraction
//of the string, unless this is what you want.
ABCBA*BbC*V*BC*AB
_ABCBA*BBC*V*BC*AB

RESULT:
ABCBA*B*C*V*BC*AB == ABCBABCVBCAB

もちろん、これはlength = 2から始まり、L / 2に増やして、繰り返します。

私は他に2つのアプローチも考えています。

  1. digraph-データを使用してステートフルな有向グラフを設定し、文字列を使用して反復します。サイクルが見つかった場合は、重複が発生します。これらのサイクルのチェックチェックがどれほど簡単かはわかりません...おそらく動的計画法なので、以下の方法2と同等である可能性があります。これについてももっと長く考えなければなりません。
  2. 距離行列-レーベンシュタイン距離行列を使用すると、コスト0で対角線の動き（対角線から外れる）からの重複を検出できる場合があります。これは、データの重複を示している可能性があります。これについてもっと考えなければなりません。
于 2008-09-11T17:47:59.247 に答える
2

この問題を解決するために私が書いたC＃アプリを次に示します。


aabccacdcd を取る

出力
abcacd

おそらくかなり乱雑に見えますが、動的なパターンの長さのビットを理解するのに少し時間がかかりました.

class Program
{
    private static List<string> values;
    private const int MAX_PATTERN_LENGTH = 4;

    static void Main(string[] args)
    {
        values = new List<string>();
        values.AddRange(new string[] { "a", "b", "c", "c", "a", "c", "d", "c", "d" });


        for (int i = MAX_PATTERN_LENGTH; i > 0; i--)
        {
            RemoveDuplicatesOfLength(i);
        }

        foreach (string s in values)
        {
            Console.WriteLine(s);
        }
    }

    private static void RemoveDuplicatesOfLength(int dupeLength)
    {
        for (int i = 0; i < values.Count; i++)
        {
            if (i + dupeLength > values.Count)
                break;

            if (i + dupeLength + dupeLength > values.Count)
                break;

            var patternA = values.GetRange(i, dupeLength);
            var patternB = values.GetRange(i + dupeLength, dupeLength);

            bool isPattern = ComparePatterns(patternA, patternB);

            if (isPattern)
            {
                values.RemoveRange(i, dupeLength);
            }
        }
    }

    private static bool ComparePatterns(List<string> pattern, List<string> candidate)
    {
        for (int i = 0; i < pattern.Count; i++)
        {
            if (pattern[i] != candidate[i])
                return false;
        }

        return true;
    }
}

質問の値と一致するように初期値を修正しました

于 2008-09-11T19:30:46.020 に答える
1

それらをすべて、お気に入りの Set 実装にダンプします。

編集:質問を理解したので、元のソリューションがこれを行うための最良の方法のように見えます。配列を 1 回ループして、保持する要素をマークするフラグの配列と、新しい配列のサイズを追跡するカウンターを保持します。次に、もう一度ループして、すべてのキーパーを新しい配列にコピーします。

于 2008-09-11T16:12:23.610 に答える
0

文字列を Set にダンプできれば、それが最も簡単な解決策であることに同意します。

何らかの理由で Set 実装にアクセスできない場合は、文字列をアルファベット順に並べ替えてから、一度調べて重複を削除します。それらを並べ替えてリストから重複を削除する方法は、コードを実行している言語と環境によって異なります。

編集：ああ、いや....あなたの明確化に基づいて、パターンが別々の行でも発生する可能性があると予想していることがわかります。私のアプローチはあなたの問題を解決しません。ごめん。ここで質問です。次のファイルがあった場合。

a

a

b

c

c

a

a

b

c

c

単純化すると思いますか

a

b

c

于 2008-09-11T16:16:23.710 に答える