Tupel zusammenfassen (rekursiv)

[polypus]

Hallo.
Ich habe ein kleines kniffliges Problem. Ich komm grad nicht drauf, wie ich das am besten lösen kann, auch weil ich schon länger nicht mehr sowas gemacht habe.

Ich habe eine liste von tupeln:
z.B. so:

Code: Alles auswählen

x = [(13, 27), (40, 47), (50, 68), (243, 247), (257, 270)]

Die tupel haben immer 2 Elemente und sind immer sortiert.
Ich will jetzt tupel zusammenfassen, wenn sie weniger als ein bestimmter wert (mal gap genannt) getrennt sind

Code: Alles auswählen

x[i+1][0] - x[i][1] <= gap

D.h., wenn ich alle tupel kombinieren will, die "näher" sind als 15 sollte die liste am Ende so aussehen:

Code: Alles auswählen

[(13, 68), (243, 270)]

Ich wollte das eigentlich rekursiv lösen, aber ich habe mich irgendwie verwurstelt und komm nicht mehr aus meiner Rekursion raus
Ich denke, dass das eigentlich recht einfach sein sollte, aber wie gesagt, ich komm momentan nicht weiter.

Code: Alles auswählen

def join_tuples(tlist, gap):
	for i in range(len(tlist)-1):
		if tlist[i+1][0]-tlist[i][1] <= gap:
			f= tlist[:i]
			e= tlist[i+2:]
			new_list = f
			new_list.append((tlist[i][0], tlist[i+1][1]))
			new_list.extend(e)
			join_tuples(new_list, gap)
		else:
			print i, len(tlist), tlist
			return tlist
			break
	else:
		continue

Kann mir wer helfen?

[BlackJack]

@polypus: Warum sich das Leben unnötig mit einer Rekursion verkomplizieren? Nahezu ungetestet:

Code: Alles auswählen

from functools import partial


def _merge(gap, result, b):
    if not result:
        return [b]
    else:
        a = result[-1]
        if b[0] - a[1] <= gap:
            result[-1] = (a[0], b[1])
        else:
            result.append(b)
        return result


def main():
    data = [(13, 27), (40, 47), (50, 68), (243, 247), (257, 270)]
    result = reduce(partial(_merge, 15), data, [])
    print result



if __name__ == '__main__':
    main()

[polypus]

Danke, BlackJack.
Jetzt muss ich nur noch versuchen, zu verstehen, was partial genau macht...
Und ich habe reduce noch nie verwendet. Das ist in dem Fall ja sehr hilfreich.

[snafu]

Nicht-rekursive Lösung ohne `reduce()` und mit Verwendung eines Generators:

Code: Alles auswählen

def iter_compressed(elems, gap):
    start = stop = None
    for elem in elems:
        if start is None:
            start = elem[0]
        if elem[1] - elem[0] <= gap:
            stop = elem[1]
        else:
            yield (start, elem[1])
            start = stop = None
    if stop is not None:
        yield (start, stop)

def compress(elems, gap):
    return list(iter_compressed(elems, gap))

[Sirius3]

@snafu: da haben sich noch ein paar kleine Fehlerchen eingeschlichen...

Code: Alles auswählen

def iter_compressed(elems, gap):
    ielems = iter(elems)
    start, stop = next(ielems)
    for elem in ielems:
        if elem[0]-stop <= gap:
            stop = elem[1]
        else:
            yield (start, stop)
            start, stop = elem
    yield (start, stop)

[snafu]

@Sirius3: Genau genommen hab ich die Aufgabenstellung etwas falsch verstanden. Ich dachte wirklich, es würde darum gehen, dass innerhalb eines Tupels der Abstand eine bestimmte Größe nicht überschreiten darf. Es war aber offenbar der Abstand vom Ende des einen Tupels bis zum Anfang des nächsten Tupels gemeint.

Das mit der "nach vorne schauenden" `for`-Schleife in deinem Code ist eine gute Idee. So spart man sich den ständigen Test auf `None` bzw die zusätzliche Komplexität.