Schreiben Sie einen Intervall Union Algorithmus funktional

Question

Angenommen, wir haben ein Array von Intervallen [(a1, b1), (a2, b2), ... , (an, bn)] sortiert in Bezug auf Startpositionen und Länge. Wir wollen alle sich überschneidenden Intervalle vereinen. Hier ist ein kleiner Beispieldatensatz, der mindestens zwei isolierte Gruppen von Intervallen enthält:

from random import randint 

def gen_interval(min, max): 
    return sorted((randint(min, max), randint(min, max))) 


sample = sorted([gen_interval(0, 100) for _ in xrange(5)] + 
       [gen_interval(101, 200) for _ in xrange(5)], 
       key=lambda (a, b): (a, b - a)) 

Und ein paar Funktionen benötigen wir für Kreuzung zu überprüfen und Intervalle zu verlängern.

def intersects(interval1, interval2): 
    a1, b1 = interval1 
    a2, b2 = interval2 
    return (a1 <= a2 <= b1) or (a1 <= b2 <= b1) 


def extend(interval1, interval2): 
    a1, b1 = interval1 
    a2, b2 = interval2 
    return (a1, b2) if b2 > b1 else (a1, b1) 

Wir können einfach die Aufgabe, unter Verwendung von Standard imperativen Programmierung erreichen:

result = [] 
for interval in sample: 
    if result and intersects(result[-1], interval): 
     result[-1] = extend(result[-1], interval) 
    else: 
     result.append(interval) 

Aber ich möchte dies mit der funktionalen Programmierung neu zu schreiben. Mein engstener Schuss ist:

subsets = [] 
for interval in sample: 
    if subsets and any(intersects(x, interval) for x in subsets[-1]): 
     subsets[-1].append(interval) 
    else: 
     subsets.append([interval]) 

result = map(lambda x: reduce(extend, x), subsets) 

hier die Hälfte der Arbeit funktionell gemacht wird, aber ich habe immer noch die ursprüngliche Array mit einem zwingenden Ansatz zu spalten. Wie kann ich die Sache mit reiner funktionaler Programmierung erledigen? Vielen Dank im Voraus.

Answer 1

Sie waren nahe mit der Verwendung von reduce. Diese Lösung akkumuliert die Liste der reduzierten Intervalle mit reduziert.

def unite_intervals(intervals): 
    def f(acc, element): 
     if acc and intersects(acc[-1], element): 
      return acc[:-1] + [extend(acc[-1], element)] 
     else: 
      return acc + [element] 
    return reduce(f, intervals, []) 

Auch dann, wenn diese eine Tonne Neuzuteilung da ich verwende + auf Liste Objekte das Ergebnis zu akkumulieren. Bei sehr großen Listen ist dies ineffizient. Sie können mit etwas wie der Bibliothek pyrsistent nach effizienteren Datenstrukturen suchen, in denen sie sich ansammeln können.