2

给定一个有序一维数组的元组(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]。

编辑请注意，数组可以是浮点数或整数。

抱歉，如果这令人困惑；我现在找不到更容易的词。任何帮助是极大的赞赏！

EDIT2 / answer我只是意识到我在提出问题时很糟糕。我最终解决了我想要的问题：

 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

我确信有不同的方法可以做到这一点，我会使用合并算法遍历两个数组，跟踪重叠区域。如果您不熟悉这个想法，请看一下merge-sort，希望在它和代码之间很清楚它是如何工作的。

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

请注意，此处的 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 回答