0

範囲のリストがパスと交差するかどうかを確認するために、次のメソッドを作成しました。別の言い方をすれば、範囲はネストされていません。

def check_ranges(lst):
    for i in range(len(lst)):
        for j in range(i+1,len(lst)):
            # (a,b) and (x,y) are being compared
            a = lst[i][0]
            b = lst[i][1]
            x = lst[j][0]
            y = lst[j][1]

            #both of these conditions mean that they cross
            if x < a and b > y:
                return True
            if x > a and b < y:
                return True
    return False

最初はfalseを返し、2番目はtrueを返す必要があります。

check_ranges([(7,16),(6,17),(5,18),(4,19)])
check_ranges([(5,16),(6,17),(5,18),(4,19)])

現在のように動作しますが、実際には非効率のようです。これが一般的な問題である場合、またはより効率的な解決策がある場合、誰かが今いますか？

4

2 に答える 2

5

並べ替えることができます。これにより、少なくとも開始点が並べ替えられた順序になります。次に、エンドポイントを前のエントリと照合するだけで済みます。小さくする必要があります：

from itertools import islice

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + (elem,)
        yield result

def check_ranges(lst):
    return any(a[1] < b[1] for a, b in window(sorted(lst)))

ここでは、古いitertoolsドキュメントページのwindowサンプルツールを使用して、スライディングウィンドウを作成しています。

この実装は以下を返します：

>>> def check_ranges(lst):
...     return any(a[1] < b[1] for a, b in window(sorted(lst)))
... 
>>> check_ranges([(7,16),(6,17),(5,18),(4,19)])
False
>>> check_ranges([(5,16),(6,17),(5,18),(4,19)])
True

エンドポイントの一致が問題になるかどうかは完全には明らかではありません。そうでない場合は、代わり<にを<=テストに変更できます。

于 2012-11-25T20:45:22.563 に答える
0

「クロスオーバー」を検出するために使用しているアルゴリズムについてはよくわかりませんが、理解度とany：を使用してコードを簡略化できます。

return any((x<a and b<y or x>a and b<y) 
            for i,(a,b) in enumerate(lst) 
            for (x,y) in lst[i:])
于 2012-11-25T20:45:29.870 に答える