9

始点と終点のペアのシーケンスは多数あります。すべてのシーケンスに含まれるすべての範囲を見つける方法は? start と end は整数であり、遠く離れている可能性があるため、シーケンスのビットフィールドを作成して&それらを -ing することは現実的ではありません。1 つの「行」(つまり 1 つのシーケンス) の範囲 (つまり、開始と終了のペア) は重複しません。また、開始と終了には下限と上限があり、32 ビット整数で十分だと思います (つまり、0 <= 値 <= 65535)。

例を挙げてみましょう：

|----------|       |---------------------|           |----------|
     |----------------------|                      |-------|
                |---------------------|                 |--|

結果は次のようになります。

                   |--------|                           |--|

上記の例は、およそ次のようになります。

row1 = (100, 200), (300, 600), (800, 900)
row2 = (140, 450), (780, 860)
row3 = (280, 580), (820, 860)
result = (300, 450), (820, 860)

また、これに関する既知のアルゴリズムはありますか? つまり、この問題には名前がありますか？

4

3 に答える 3

8

各シーケンスの範囲が重複しないと仮定すると、それほど難しいことではありません。この場合、すべてのポイントを繰り返し処理し、範囲に出入りするときに追跡するだけです。

すべてのシーケンスからすべてのポイントを 1 つのリストに入れ、それを並べ替えて、各ポイントが開始点か終了点かを覚えておいてください。

100 S ---
140 S  |   ---
200 E ---   |
280 S       |  ---
300 S ---   |   |
450 E  |   ---  |
580 E  |       ---
600 E ---
780 S      ---
800 S ---   |
820 S  |    |  ---
860 E  |   ---  |
860 E  |       ---
900 E ---

次に、このリストを反復処理し、開始点に遭遇するたびにカウンターをインクリメントし、終点に遭遇するたびにカウンターを減少させます。

      0
100 S 1
140 S 2
200 E 1
280 S 2  
300 S 3 <--
450 E 2 <--
580 E 1
600 E 0
780 S 1
800 S 2
820 S 3 <--
860 E 2 <--
860 E 1
900 E 0

カウンターがシーケンスの数 (この例では 3 つ) に等しい場合、1 つの範囲の開始点が見つかり、次のポイントがこの範囲の終了点になります。

各シーケンスの範囲が start でソートされている場合、または start でソートできる場合は、リストを明示的に作成する必要さえないことに注意してください。この場合、各シーケンスの現在の範囲へのポインターを保持することで、すべてのシーケンスを並列に反復処理できます。

ここでは、C# の全体 - 範囲のクラスです。

internal sealed class Range
{
    private readonly Int32 start = 0;

    private readonly Int32 end = 0;

    public Range(Int32 start, Int32 end)
    {
        this.start = start;
        this.end = end;
    }

    internal Int32 Start
    {
        get { return this.start; }
    }

    internal Int32 End
    {
        get { return this.end; }
    }
}

始点と終点を区別するためのフラグを持つポイントのクラス。

internal sealed class Point
{
    private readonly Int32 position = 0;

    private readonly Boolean isStartPoint = false;

    public Point(Int32 position, Boolean isStartPoint)
    {
        this.position = position;
        this.isStartPoint = isStartPoint;
    }

    internal Int32 Position
    {
        get { return this.position; }
    }

    internal Boolean IsStartPoint
    {
        get { return this.isStartPoint; }
    }
}

最後に、アルゴリズムとテスト プログラムです。

internal static class Program
{
    private static void Main()
    {
        var s1 = new List<Range> { new Range(100, 200), new Range(300, 600), new Range(800, 900) };
        var s2 = new List<Range> { new Range(140, 450), new Range(780, 860) };
        var s3 = new List<Range> { new Range(280, 580), new Range(820, 860) };

        var sequences = new List<List<Range>> { s1, s2, s3 };

        var startPoints = sequences.SelectMany(sequence => sequence)
                                   .Select(range => new Point(range.Start, true));

        var endPoints   = sequences.SelectMany(sequence => sequence)
                                   .Select(range =>  new Point(range.End, false));

        var points = startPoints.Concat(endPoints).OrderBy(point => point.Position);

        var counter = 0;

        foreach (var point in points)
        {
            if (point.IsStartPoint)
            {
                counter++;

                if (counter == sequences.Count)
                {
                    Console.WriteLine("Start {0}", point.Position);
                }
            }
            else
            {
                if (counter == sequences.Count)
                {
                    Console.WriteLine("End   {0}", point.Position);
                    Console.WriteLine();
                }

                counter--;
            }
        }

        Console.ReadLine();
    }
}

出力は次のとおりです。

Start 300
End   450

Start 820
End   860
于 2013-01-10T18:24:52.177 に答える
5

シーケンスを2つずつ融合するだけで、それができると思います。

各融合は、考慮されるシーケンスの間隔数の線形時間で実行可能である必要があり (シーケンスがソートされている場合)、M-1 融合が必要です (M 数のシーケンスで)。

例を挙げて、追加のシーケンスを追加します。

|----------|       |---------------------|           |----------|
     |----------------------|                      |-------|
                |---------------------|                 |--|
        |-----------------------------------|           |-----|

シーケンスのペアによる融合:

     |-----|       |--------|                        |-----|
                |---------------------|                 |--|

再度融合:

                   |--------|                           |--|

しかし、それを行うためのより速い方法を見つけることができるかもしれません。最悪のケースでは、O(N log M) 実行時間 (合計 N 間隔) になります。

編集：融合のための擬似コード

Take s1 and s2 an iterator on each sequence
While there are still intervals in both sequences
    Compare the intervals:
    If s1.begin < s2.begin
        If s2.begin < s1.end
            If s2.end > s1.end
                Add [s2.begin,s1.end] to the fused sequence
                Increment s1
            Else
                Add [s2.begin,s2.end] to the fused sequence
                Increment s2
        Else
            Increment s1
    Else
        Same thing with s1 and s2 reversed
于 2013-01-10T18:15:25.133 に答える
0

これは最長共通部分文字列と呼ばれます。接尾辞ツリーを使用して解決できます。このブログで入手できる非常にきれいな Java 実装があり、2 つ以上のソース文字列で動作します。

あなたがキャラクターを扱っているかどうかはわかりませんが、そうでない場合はおそらくそれを適応させることができると確信しています.

于 2013-01-10T17:53:15.200 に答える