4

「から」と「から」の時間を示すタプルでいっぱいのリストがあるとします。

tuples = [ (0, 5), (5, 10), (10, 15), (15,20) ]

そして、特定のタプルと重複するタプルのリストを取得できるようにしたい:

searchTuple = (3,11)
result = findOverlap(tuples, searchTuple)

このコードは次のリストを返します。

[ (0, 5), (5, 10), (10, 15) ]

(16, 22) の searchTuple は、最後のタプル (15,20) のみを返す必要があります。

この検索をコーディングする最も効率的な方法は何ですか? いろいろ試してみましたが、アルゴリズムがうまく動作しません。キャッチすることに興味がある次のさまざまな「重複」を考えました。

a) tuple_min < find_min AND tuple_max > find_max

search tuple -> |         | 
            |----------------| the search tuple is entirely contained

b) tuple_min > find_min AND tuple_max > find_max

         |         |
            |----------------| the left part of the tuple overlaps

c) tuple_min < find_min AND tuple_max < find_max

              |         |
    |----------------| the right part of the tuple overlaps

しかし、これを実装して得た結果は、間違った結果になってしまいました...私の考えはどこが間違っていますか?

4

6 に答える 6

3

手早く汚いリストの理解:

>>> t = [ (0, 5), (5, 10), (10, 15), (15,20) ]
>>> o = (3,11)
>>> [(i[0],i[1]) for i in t if i[0] >= o[0] and i[0] <= o[1] or i[1] >= o[0] and i[1] <= o[1]]
#returns: 
[(0, 5), (5, 10), (10, 15)]
>>> o = (16,22)
#returns
[(15, 20)]
于 2013-07-25T20:13:01.693 に答える
1

この方法は初心者にやさしく、うまくいくはずです

def findOverlap(tuples, searchTuple):
  result=[]
  for tuple in tuples:
    if searchTuple[0] in range(tuple[0],tuple[1]): #search for the first value
      result.append(tuple)
      continue
    if len(result)>0 and searchTuple[1] in range(tuple[0],tuple[1]): #search for the last value
      result.append(tuple)
      break
    if len(result)>0:
      result.append(tuple) #add all elements between first and last
  return result

range(tuple[0],tuple[1])すべての数値を一方から他方に返すだけなので、(5,10)タプルを調べると返されます[5,6,7,8,9,10]

次にsearchTuple[0] in range(tuple[0],tuple[1])、searchTuple の最初の要素がその範囲内にあるかどうかを確認します。

result.append(tuple)メソッドから返されるもののリストにそのタプルを追加します。

残りはループ操作と書式設定です。

于 2013-07-25T19:56:49.910 に答える