2

順序付けられた1D配列のタプルが与えられた場合、配列が最大の共通範囲にまたがるように、(arr1, arr2, arr3, )最小/最大インデックスのタプルを取得するための最良の方法はどれでしょうか。((min1, max1), (min2, max2), (min3, max3), )

私が言いたいのは

min(arr[min1], arr2[min2], arr3[min3]) > max(arr1[min1-1], arr2[min2-1], arr3[min3-1])

と

max(arr[min1], arr2[min2], arr3[min3]) < min(arr1[min1+1], arr2[min2+1], arr3[min3+1])

上限についても同じですか？

例：

与えられarange(12)てarange(3, 8)、私は取得したい((3,8), (0,6))、という目標を持っていarange(12)[3:8] == arange(3,8)[0:6]ます。

編集配列はfloatまたは整数である可能性があることに注意してください。

これが紛らわしい場合は申し訳ありません。今はもっと簡単な言葉が見つかりません。どんな助けでも大歓迎です！

EDIT2/回答私は自分の質問を作成するのがひどいことに気づきました。私はこのように私が望んでいたことを解決することになりました：

 mins = [np.min(t) for t in arrays]
 maxs = [np.max(t) for t in arrays]
 lower_bound = np.max(mins)
 upper_bound = np.min(maxs)
 lower_row = [np.searchsorted(arr, lower_bound, side='left') for arr in arrays]
 upper_row = [np.searchsorted(arr, upper_bound, side='right') for arr in arrays]
 result = zip(lower_row, upper_row)

ただし、どちらの回答も私が尋ねた質問に対して有効であるように思われるため、どちらか一方だけを「正しい」として選択するかどうかはわかりません。どうすればよいですか。

4

2 に答える 2

1

これを行うにはさまざまな方法があると確信しています。マージアルゴリズムを使用して2つの配列をウォークスルーし、オーバーラップ領域を追跡します。アイデアに慣れていない場合は、マージソートを見てください。うまくいけば、それとコードの間で、これがどのように機能するかが明確になります。

def find_overlap(a, b):
    i = 0
    j = 0
    len_a = len(a)
    len_b = len(b)
    in_overlap = False
    best_count = 0
    best_start = (-1, -1)
    best_end = (-1, -1)

    while i < len_a and j < len_b:

        if a[i] == b[j]:
            if in_overlap:
                # Keep track of the length of the overlapping region
                count += 1
            else:
                # This is a new overlapping region, set count to 1 record start
                in_overlap = True
                count = 1
                start = (i, j)
            # Step indicies
            i += 1
            j += 1
            end = (i, j)
            if count > best_count:
                # Is this the longest overlapping region so far?
                best_count = count
                best_start = start
                best_end = end
        # If not in a an overlapping region, only step one index
        elif a[i] < b[j]:
            in_overlap = False
            i += 1
        elif b[j] < a[i]:
            in_overlap = False
            j += 1
        else:
            # This should never happen
            raise
    # End of loop

    return best_start, best_end

ここでの終わりはPython規則で返されるため、ifa=[0, 1, 2]とb=[0, 1, 4]、、start=(0, 0)およびend=(2, 2)。

于 2013-01-21T21:30:58.290 に答える
1

私はあなたが最も長い一般的な部分文字列の問題の特別な場合の解決策を探していると思います。この問題は接尾辞木または動的計画法を使用して解決できますが、ソートされた「文字列」の特殊なケースの方が簡単に解決できます。

これがあなたが望む値を与えると私が思うコードです。単一の引数は、ソートされたシーケンスのシーケンスです。その戻り値は、内部シーケンスごとに2タプルを含むリストです。タプル値は、シーケンス間の最長の共通サブストリングへのスライスインデックスです。共通の部分文字列がない場合、タプルはすべてになり(0,0)、空のスライスになります（空のスライスはすべて互いに等しくなるため、これは正しいと思います）。

コード：

def longest_common_substring_sorted(sequences):
    l = len(sequences)
    current_indexes = [0]*l
    current_substring_length = 0
    current_substring_starts = [0]*l
    longest_substring_length = 0
    longest_substring_starts = current_substring_starts

    while all(index < len(sequence) for index, sequence
              in zip(current_indexes, sequences)):
        m = min(sequence[index] for index, sequence
                in zip(current_indexes, sequences))
        common = True
        for i in range(l):
            if sequences[i][current_indexes[i]] == m:
                current_indexes[i] += 1
            else:
                common = False

        if common:
            current_substring_length += 1
        else:
            if current_substring_length > longest_substring_length:
                longest_substring_length = current_substring_length
                longest_substring_starts = current_substring_starts
            current_substring_length = 0
            current_substring_starts = list(current_indexes)

    if current_substring_length > longest_substring_length:
        longest_substring_length = current_substring_length
        longest_substring_starts = current_substring_starts

    return [(i, i+longest_substring_length)
            for i in longest_substring_starts]

テスト出力：

>>> a=[1,2,3,4,5,6]
>>> b=[1,2,3,5,6,7]
>>> c=[3,4,5,6,7,8]
>>> longest_common_substring_sorted((a,b,c))
[(4, 6), (3, 5), (2, 4)]

コードにコメントが上手くいかなかったことをお詫びします。アルゴリズムは、マージソートのマージステップにいくぶん似ています。基本的に、各シーケンスへのインデックスを追跡します。繰り返すと、最小値に等しい値に対応するすべてのインデックスがインクリメントされます。すべてのリストの現在の値が等しい場合（最小値、つまり互いに）、すべてのリストに共通のサブストリング内にあることがわかります。サブストリングが終了すると、これまでに見つかった最長のサブストリングと照合されます。

于 2013-01-21T21:31:15.137 に答える