Wie überlappende Nummernbereiche funktional aus einer Liste zusammengeführt werden

7

Ich habe eine Reihe von Bereichsobjekten, die ich zusammenführen muss, damit alle überlappenden Bereiche verschwinden:

%Vor%

Hier sind die Bereiche:

%Vor%

Wenn wir fertig sind, bekommen wir:

%Vor%

Imperativer Algorithmus:

  1. Pop () das erste range-obj und iteriere durch den Rest der Liste und vergleiche es mit jedem der anderen Bereiche.
  2. wenn es einen überlappenden Gegenstand gibt, füge sie zusammen (dies ergibt eine neue Range-Instanz) und lösche die 2 Merge-Kandidaten aus der Source-Liste.
  3. Am Ende der Liste fügen Sie das Range-Objekt (das sich durch Zusammenführen mehrfach hätte ändern können) in die Endergebnisliste ein.
  4. Wiederholen Sie dies mit dem nächsten der verbleibenden Elemente.
  5. Sobald die Quellenliste leer ist, sind wir fertig.

Um dies zwingend zu machen, muss man viele temporäre Variablen, indizierte Schleifen usw. erstellen.

Ich frage mich also, ob es einen funktionelleren Ansatz gibt?

Auf den ersten Blick muss die Quellensammlung in der Lage sein, sich wie ein Stapel zu verhalten, indem sie pop () PLUS bereitstellt die Möglichkeit geben, Elemente nach Index zu löschen, während man darüber iteriert, aber das wäre dann nicht mehr funktional.

    
recalcitrant 09.02.2012, 21:15
quelle

3 Antworten

8

Versuche Tail-Rekursion. (Annotation wird nur benötigt, um Sie zu warnen, wenn die Tail-Recursion-Optimierung nicht stattfindet; der Compiler wird es tun, wenn es mit Anmerkungen versehen ist oder nicht.)

%Vor%     
Rex Kerr 09.02.2012, 23:26
quelle
8

Ich liebe diese Art von Puzzles:

%Vor%     
leedm777 09.02.2012 21:53
quelle
4

Hier ist meine Lösung:

%Vor%     
Dan Simon 09.02.2012 21:57
quelle