algorithm - 重複しない最長のシーケンスを見つけるアルゴリズム

Question

私は次の問題を解決するための最良の方法を見つけようとしています。最善の方法で、私はそれほど複雑ではないことを意味します。

入力として、次のようなタプル（start、length）のリスト：

[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]

各要素は、開始と長さ(5,6,7,8,9,10,11)によってシーケンスを再プリセットします。たとえば、（5,7）は、シーケンス（ 5で始まる7つの要素のリスト）と同等です。タプルはstart要素によってソートされていると見なすことができます。

出力は、最長の連続シーケンスを表すタプルの重複しない組み合わせを返す必要があります。つまり、ソリューションは、オーバーラップやギャップのない範囲のサブセットであり、可能な限り最長です。ただし、複数存在する可能性があります。

たとえば、与えられた入力の場合、解決策は次のとおりです。

[(0,5),(5,7)]に相当(0,1,2,3,4,5,6,7,8,9,10,11)

この問題を解決するための最良のアプローチをバックトラックしていますか？

私は人々が提案できるさまざまなアプローチに興味があります。

また、誰かがこの問題または同様の別の問題の正式な参照を知っている場合は、参照を取得したいと思います。

ところで-これは宿題ではありません。

編集

いくつかの間違いを避けるために、これは予想される動作の別の例です

[(0,1),(1,7),(3,20),(8,5)]正解のような入力の場合、[(3,20)]長さ20の（3,4,5、..、22）と同等です。受け取った回答の一部は[(0,1),(1,7),(8,5)]（0,1,2、...、11,12）と同等になります。正解として。しかし、はより短いため、この最後の答えは正しくありません[(3,20)]。

Answer 1

ハッシュマップを使用して特定のインデックスで終了する最長の連続シーケンスの長さを追跡しながら、指定された順序（開始要素による）を使用してタプルのリストを反復処理します。

疑似コード、ハッシュマップで見つからないアイテムなどの詳細をスキップします（見つからない場合は0が返されると想定します）：

int bestEnd = 0;
hashmap<int,int> seq // seq[key] = length of the longest sequence ending on key-1, or 0 if not found
foreach (tuple in orderedTuples) {
    int seqLength = seq[tuple.start] + tuple.length
    int tupleEnd = tuple.start+tuple.length;
    seq[tupleEnd] = max(seq[tupleEnd], seqLength)
    if (seqLength > seq[bestEnd]) bestEnd = tupleEnd
}
return new tuple(bestEnd-seq[bestEnd], seq[bestEnd])

これはO（N）アルゴリズムです。

このシーケンスを構成する実際のタプルが必要な場合は、エンドインデックスによってハッシュされたタプルのリンクリストも保持する必要があります。これは、このエンドポイントの最大長が更新されるたびに更新されます。

更新：Pythonに関する私の知識はかなり限られていますが、貼り付けたPythonコードに基づいて、長さだけでなく実際のシーケンスを返すこのコードを作成しました。

def get_longest(arr):
    bestEnd = 0;
    seqLengths = dict() #seqLengths[key] = length of the longest sequence ending on key-1, or 0 if not found
    seqTuples = dict() #seqTuples[key] = the last tuple used in this longest sequence
    for t in arr:
        seqLength = seqLengths.get(t[0],0) + t[1]
        tupleEnd = t[0] + t[1]
        if (seqLength > seqLengths.get(tupleEnd,0)):
            seqLengths[tupleEnd] = seqLength
            seqTuples[tupleEnd] = t
            if seqLength > seqLengths.get(bestEnd,0):
                bestEnd = tupleEnd
    longestSeq = []
    while (bestEnd in seqTuples):
        longestSeq.append(seqTuples[bestEnd])
        bestEnd -= seqTuples[bestEnd][1]
    longestSeq.reverse()
    return longestSeq


if __name__ == "__main__":
    a = [(0,3),(1,4),(1,1),(1,8),(5,2),(5,5),(5,6),(10,2)]
    print(get_longest(a))

Answer 2

改訂されたアルゴリズム：

create a hashtable of start->list of tuples that start there
put all tuples in a queue of tupleSets
set the longestTupleSet to the first tuple
while the queue is not empty
    take tupleSet from the queue
    if any tuples start where the tupleSet ends
        foreach tuple that starts where the tupleSet ends
            enqueue new tupleSet of tupleSet + tuple
        continue

    if tupleSet is longer than longestTupleSet
        replace longestTupleSet with tupleSet

return longestTupleSet

c＃の実装

public static IList<Pair<int, int>> FindLongestNonOverlappingRangeSet(IList<Pair<int, int>> input)
{
    var rangeStarts = input.ToLookup(x => x.First, x => x);
    var adjacentTuples = new Queue<List<Pair<int, int>>>(
        input.Select(x => new List<Pair<int, int>>
            {
                x
            }));

    var longest = new List<Pair<int, int>>
        {
            input[0]
        };
    int longestLength = input[0].Second - input[0].First;

    while (adjacentTuples.Count > 0)
    {
        var tupleSet = adjacentTuples.Dequeue();
        var last = tupleSet.Last();
        int end = last.First + last.Second;
        var sameStart = rangeStarts[end];
        if (sameStart.Any())
        {
            foreach (var nextTuple in sameStart)
            {
                adjacentTuples.Enqueue(tupleSet.Concat(new[] { nextTuple }).ToList());
            }
            continue;
        }
        int length = end - tupleSet.First().First;
        if (length > longestLength)
        {
            longestLength = length;
            longest = tupleSet;
        }
    }

    return longest;
}

テスト：

[Test]
public void Given_the_first_problem_sample()
{
    var input = new[]
        {
            new Pair<int, int>(0, 5),
            new Pair<int, int>(0, 1),
            new Pair<int, int>(1, 9),
            new Pair<int, int>(5, 5),
            new Pair<int, int>(5, 7),
            new Pair<int, int>(10, 1)
        };
    var result = FindLongestNonOverlappingRangeSet(input);
    result.Count.ShouldBeEqualTo(2);
    result.First().ShouldBeSameInstanceAs(input[0]);
    result.Last().ShouldBeSameInstanceAs(input[4]);
}

[Test]
public void Given_the_second_problem_sample()
{
    var input = new[]
        {
            new Pair<int, int>(0, 1),
            new Pair<int, int>(1, 7),
            new Pair<int, int>(3, 20),
            new Pair<int, int>(8, 5)
        };
    var result = FindLongestNonOverlappingRangeSet(input);
    result.Count.ShouldBeEqualTo(1);
    result.First().ShouldBeSameInstanceAs(input[2]);
}

Answer 3

これは、重み付き有向非巡回グラフの最長パス問題の特殊なケースです。

グラフのノードは、開始点とシーケンスの最後の要素の後のポイントであり、次のシーケンスが開始される可能性があります。

2つのノード間の距離はパスに関係なく同じでなければならないため、この問題は特別です。

Answer 4

テストされていないため、以前のソリューションを削除しました。

問題は、「加重有向非巡回グラフ」で最長のパスを見つけることです。線形時間で解決できます。

http://en.wikipedia.org/wiki/Longest_path_problem#Weighted_directed_acyclic_graphs

{開始位置}ユニオン{​​（開始位置+終了位置）}のセットを頂点として配置します。あなたの例では、{0、1、5、10、11、12}になります。

頂点v0、v1の場合、v0 + w =​​ v1となる終了値wがある場合は、v0をv1に接続する有向エッジを追加し、その重みとしてwを入力します。

次に、ウィキペディアページの擬似コードに従います。頂点の数は2xnの最大値（nはタプルの数）であるため、問題は線形時間で解決できます。

Answer 5

擬似コードを実際のPythonコードに置き換えるために編集

コードを変更するためにもう一度編集しました。元のアルゴリズムが解決策にありましたが、ペアの2番目の値が何であるかを誤解しました！フォーチュナテリーの基本的なアルゴリズムは同じで、変更することができました。

これは、O（N log N）の問題を解決し、ハッシュマップを使用しない（つまり、隠れた時間はない）アイデアです。メモリには、N*2の「もの」を使用します。

各タプルにさらに2つの値（BackCount、BackLink）を追加します。組み合わせが成功すると、BackLinkは右から左に右端のタプルから左端のタプルにリンクします。BackCountは、指定されたBackLinkの累積カウント値になります。

ここにいくつかのPythonコードがあります：

def FindTuplesStartingWith(tuples, frm):
    # The Log(N) algorithm is left as an excersise for the user
    ret=[]
    for i in range(len(tuples)):
        if (tuples[i][0]==frm): ret.append(i)
    return ret

def FindLongestSequence(tuples):

    # Prepare (BackCount, BackLink) array
    bb=[] # (BackCount, BackLink)
    for OneTuple in tuples: bb.append((-1,-1))

    # Prepare
    LongestSequenceLen=-1
    LongestSequenceTail=-1

    # Algorithm
    for i in range(len(tuples)):
        if (bb[i][0] == -1): bb[i] = (0, bb[i][1])
        # Is this single pair the longest possible pair all by itself?
        if (tuples[i][1] + bb[i][0]) > LongestSequenceLen:
            LongestSequenceLen = tuples[i][1] + bb[i][0]
            LongestSequenceTail = i
        # Find next segment
        for j in FindTuplesStartingWith(tuples, tuples[i][0] + tuples[i][1]):
            if ((bb[j][0] == -1) or (bb[j][0] < (bb[i][0] + tuples[i][1]))):
                # can be linked
                bb[j] = (bb[i][0] + tuples[i][1], i)
                if ((bb[j][0] + tuples[j][1]) > LongestSequenceLen):
                    LongestSequenceLen = bb[j][0] + tuples[j][1]
                    LongestSequenceTail=j

    # Done! I'll now build up the solution
    ret=[]
    while (LongestSequenceTail > -1):
        ret.insert(0, tuples[LongestSequenceTail])
        LongestSequenceTail = bb[LongestSequenceTail][1]
    return ret

# Call the algoritm
print FindLongestSequence([(0,5), (0,1), (1,9), (5,5), (5,7), (10,1)])
>>>>>> [(0, 5), (5, 7)]
print FindLongestSequence([(0,1), (1,7), (3,20), (8,5)])    
>>>>>> [(3, 20)]

アルゴリズム全体の鍵は、「THISISTHEKEY」コメントがコードのどこにあるかです。現在のStartTupleをEndTupleにリンクできることはわかっています。EndTuple.Toで終わる長いシーケンスが存在する場合は、小さいStartTuple.Fromで開始する必要があり、配列が「From」でソートされているため、この時点までに検出されました。

Answer 6

これは単純なreduce操作です。連続するタプルのペアが与えられると、それらを組み合わせることができるか、できないかのどちらかです。したがって、ペアワイズ組み合わせ関数を定義します。

def combo(first,second):
    if first[0]+first[1] == second[0]:
        return [(first[0],first[1]+second[1])]
    else:
        return [first,second]

これは、2つの引数を組み合わせた1つの要素、または元の2つの要素のリストを返すだけです。

次に、最初のリストを反復処理してペアを組み合わせる関数を定義します。

def collapse(tupleList):
    first = tupleList.pop(0)
    newList = []
    for item in tupleList:
        collapsed = combo(first,item)
        if len(collapsed)==2:
            newList.append(collapsed[0])
        first = collapsed.pop()
    newList.append(first)
    return newList

これにより、リスト内の現在のアイテム（2番目のアイテムから開始）と比較する最初の要素が保持され、それらを組み合わせることができない場合は、最初の要素が新しいリストにドロップされ、first2つのうちの2番目の要素に置き換えられます。

collapse次に、タプルのリストを呼び出します。

>>> collapse( [(5, 7), (12, 3), (0, 5), (0, 7), (7, 2), (9, 3)] )
[(5, 10), (0, 5), (0, 12)]

[編集]最後に、結果を繰り返し処理して、最長のシーケンスを取得します。

def longest(seqs):
    collapsed = collapse(seqs)
    return max(collapsed, key=lambda x: x[1])

[/編集]

複雑さO（N）。pop(0)ボーナスマークの場合は、イテレータがapop()になり、配列のインデックスを再作成したり、代わりにイテレータを移動したりする必要がないように、逆に実行します。reduceトップマークの場合は、マルチスレッドの良さのためのペアワイズ操作として実行します。

Answer 7

基本的な用語でアルゴリズムを考えるだけで、これは機能しますか？

（ひどい構文についてはお詫びしますが、ここでは言語に依存しないようにしています）

最初に最も単純な形式：最も長い連続したペアを見つけます。

すべてのメンバーを循環し、startposが高い他のすべてのメンバーと比較します。2番目のメンバーのstartposが、最初のメンバーのstartposと長さの合計に等しい場合、それらは連続しています。もしそうなら、これを表すために、より低いstartposと結合された長さで新しいセットに新しいメンバーを形成します。

次に、これらのペアのそれぞれを取得し、開始位置が高いすべての単一メンバーと比較して繰り返し、連続するトリプルの新しいセットを形成します（存在する場合）。

新しいセットがなくなるまで、このパターンを続けます。

トリッキーな部分は、実際の最長のチェーンを見つけるために、各セットのすべてのメンバーの長さを比較する必要があることです。

これは他の方法ほど効率的ではないと確信していますが、これはこのソリューションを総当たり攻撃するための実行可能なアプローチであると思います。

これと私が見落としているかもしれないエラーについてのフィードバックをいただければ幸いです。

Answer 8

• すべての開始点と終了点の順序付けられた配列を作成し、それらすべてを1つに初期化します
• タプル内の各アイテムについて、エンドポイント（開始と終了）を配列内の順序付けられたアイテムと比較します。それらの間にポイントがある場合（たとえば、配列内のポイントが5で、長さが4の開始2がある場合）、値を次のように変更します。零。
• ループが終了したら、順序付けられた配列を移動し始め、1が表示されたらストリップを作成し、1が表示されている間に既存のストリップにゼロを追加し、ストリップを閉じます。
• 最後にストリップの長さを確認してください

複雑さはO（4-5 * N）くらいだと思います

（更新を参照）

Nはタプル内のアイテムの数です。

---

アップデート

ご存知のように、複雑さは正確ではありませんが、線の伸び（タプルアイテム）の数の関数であるため、非常に小さいことは間違いありません。

したがって、Nが線のストレッチの数である場合、並べ替えはO（2N * log2N）になります。比較はO（2N）です。線の伸びを見つけることもO（2N）です。つまり、全体としてO（2N（log2N + 2））です。

Answer 9

これは完璧な「動的計画法」の問題のように聞こえます...

最も単純なプログラムは、ブルートフォース（再帰など）を実行することですが、これには指数関数的な複雑さがあります。

動的計画法を使用すると、長さnの配列aを設定できます。ここで、nは問題のすべての（開始+長さ）値の最大値です。ここで、a[i]はa[i]までの最長の重複しないシーケンスを示します。次に、すべてのタプルをステップトロードして、を更新できます。このアルゴリズムの複雑さはO（n * k）になります。ここで、kは入力値の数です。