Làm cách nào để chia một tập hợp các phạm vi chồng chéo thành các phạm vi không chồng chéo?

Question

Hãy nói rằng bạn có một bộ dao động:

• 0 - 100: 'a'
• 0-75: 'b'
• 95-150: 'c'
• 120-130 : 'd'

Rõ ràng, các phạm vi này trùng lặp tại các điểm nhất định. Làm thế nào bạn sẽ mổ xẻ các phạm vi này để tạo ra một danh sách các phạm vi không trùng lặp, trong khi vẫn giữ lại thông tin liên quan đến phạm vi ban đầu của chúng (trong trường hợp này, chữ cái sau phạm vi)?

Ví dụ, kết quả của các bên trên sau khi chạy thuật toán sẽ là:

• 0 - 75: 'a', 'b'
• 76-94: 'a'
• 95 - 100: 'a', 'c'
• 101-119: 'c'
• 120-130: 'c', 'd'
• 131-150: 'c'

Answer 1

Tôi có cùng một câu hỏi khi viết một chương trình để trộn (một phần chồng chéo) các mẫu âm thanh.

Điều tôi đã làm là thêm "sự kiện bắt đầu" và "sự kiện dừng" (cho mỗi mục) vào danh sách, sắp xếp danh sách theo thời gian và sau đó xử lý theo thứ tự. Bạn có thể làm tương tự, ngoại trừ sử dụng một điểm nguyên thay vì một thời gian, và thay vì trộn âm thanh, bạn sẽ thêm các biểu tượng cho tập hợp tương ứng với một phạm vi. Cho dù bạn tạo ra các khoảng trống hoặc chỉ bỏ qua chúng sẽ là tùy chọn.

Edit Có lẽ một số mã ...

# input = list of (start, stop, symbol) tuples 
points = [] # list of (offset, plus/minus, symbol) tuples 
for start,stop,symbol in input: 
    points.append((start,'+',symbol)) 
    points.append((stop,'-',symbol)) 
points.sort() 

ranges = [] # output list of (start, stop, symbol_set) tuples 
current_set = set() 
last_start = None 
for offset,pm,symbol in points: 
    if pm == '+': 
     if last_start is not None: 
      #TODO avoid outputting empty or trivial ranges 
      ranges.append((last_start,offset-1,current_set)) 
     current_set.add(symbol) 
     last_start = offset 
    elif pm == '-': 
     # Getting a minus without a last_start is unpossible here, so not handled 
     ranges.append((last_start,offset-1,current_set)) 
     current_set.remove(symbol) 
     last_start = offset 

# Finish off 
if last_start is not None: 
    ranges.append((last_start,offset-1,current_set)) 

Hoàn toàn chưa được kiểm tra, rõ ràng.

Answer 2

Tôi muốn nói tạo danh sách các điểm cuối và sắp xếp nó, cũng lập chỉ mục danh sách các dải ô bằng cách bắt đầu và kết thúc điểm. Sau đó, lặp qua danh sách các điểm cuối được sắp xếp và cho mỗi điểm, kiểm tra các dải ô để xem các dải nào đang bắt đầu/dừng tại điểm đó.

Đây có lẽ là đại diện tốt hơn trong mã ... nếu dãy của bạn được đại diện bởi các bộ:

ranges = [(0,100,'a'),(0,75,'b'),(95,150,'c'),(120,130,'d')] 
endpoints = sorted(list(set([r[0] for r in ranges] + [r[1] for r in ranges]))) 
start = {} 
end = {} 
for e in endpoints: 
    start[e] = set() 
    end[e] = set() 
for r in ranges: 
    start[r[0]].add(r[2]) 
    end[r[1]].add(r[2]) 
current_ranges = set() 
for e1, e2 in zip(endpoints[:-1], endpoints[1:]): 
    current_ranges.difference_update(end[e1]) 
    current_ranges.update(start[e1]) 
    print '%d - %d: %s' % (e1, e2, ','.join(current_ranges)) 

Mặc dù nhìn vào này khi nhìn lại, tôi sẽ ngạc nhiên nếu không có một hiệu quả hơn (hoặc ít nhất là tìm kiếm) để làm điều đó.

Answer 3

Mã giả:

unusedRanges = [ (each of your ranges) ] 
rangesInUse = [] 
usedRanges = [] 
beginningBoundary = nil 

boundaries = [ list of all your ranges' start and end values, sorted ] 
resultRanges = [] 

for (boundary in boundaries) { 
    rangesStarting = [] 
    rangesEnding = [] 

    // determine which ranges begin at this boundary 
    for (range in unusedRanges) { 
     if (range.begin == boundary) { 
      rangesStarting.add(range) 
     } 
    } 

    // if there are any new ones, start a new range 
    if (rangesStarting isn't empty) { 
     if (beginningBoundary isn't nil) { 
      // add the range we just passed 
      resultRanges.add(beginningBoundary, boundary - 1, [collected values from rangesInUse]) 
     } 

     // note that we are starting a new range 
     beginningBoundary = boundary 

     for (range in rangesStarting) { 
      rangesInUse.add(range) 
      unusedRanges.remove(range) 
     } 
    } 

    // determine which ranges end at this boundary 
    for (range in rangesInUse) { 
     if (range.end == boundary) { 
      rangesEnding.add(range) 
     } 
    } 

    // if any boundaries are ending, stop the range 
    if (rangesEnding isn't empty) { 
     // add the range up to this boundary 
     resultRanges.add(beginningBoundary, boundary, [collected values from rangesInUse] 

     for (range in rangesEnding) { 
      usedRanges.add(range) 
      rangesInUse.remove(range) 
     } 

     if (rangesInUse isn't empty) { 
      // some ranges didn't end; note that we are starting a new range 
      beginningBoundary = boundary + 1 
     } 
     else { 
      beginningBoundary = nil 
     } 
    } 
} 

kiểm tra Đơn vị:

Cuối cùng, resultRanges nên có kết quả mà bạn đang tìm kiếm, unusedRanges và rangesInUse nên để trống, beginningBoundary nên con số không, và usedRanges nên chứa những gì unusedRanges được sử dụng để chứa (nhưng được sắp xếp theo range.end).

Answer 4

Những gì bạn mô tả là một ví dụ về lý thuyết tập hợp.Đối với một thuật toán chung của công đoàn máy tính, nút giao thông, và sự khác biệt của bộ xem:

www.gvu.gatech.edu/~jarek/graphics/papers/04PolygonBooleansMargalit.pdf

Trong khi bài báo được nhắm vào đồ họa nó được áp dụng để lý thuyết tập hợp chung là tốt. Không chính xác vật liệu đọc ánh sáng.