List merge

[yzxyyy]

Wie schreibt man eine python-Funktion merge, die als Eingabe zwei aufsteigend sortierte einfach verkettete Listen L1 und L2 erhält und daraus in linearer Laufzeit eine aufsteigend sortierte einfach verkettete Liste erstellt, welche alle Elemente von L1 und L2 enthält. Dabei du ̈rfen die Listen L1 und L2 verändert/gelöscht werden.
Vielen danke für Ihre Helfe!

[__deets__]

Was hast du schon probiert? Und wie würdest du das auf Papier machen?

[Sirius3]

@yzxyyy: wenn man Aufgaben aus geTeXten PDF-Dokumenten herauskopiert, immer aufpassen, dass Umlaute auch richtige geschrieben werden. Hier werden keine Hausaufgaben ohne Eigenleistung gelöst. Du mußt also recht konkret schreiben, was Du versucht hast und an welcher Stelle genau Dein produziertes Ergebnis von dem gewünschten abweicht.

[DeaD_EyE]

Wenn man das im Stil von Python programmiert, ist das eine Funktion mit zwei Zeilen Code.
Wenn du bestimmte built-in Funktionen (min, max, range, zip) bzw. Generatoren und auch Module nicht nutzen darfst, geht das aber auch recht einfach. Sind dann 20 Zeilen Code.

Wie würdest du einem 10 Jährigen Kind diese Aufgabe erklären?
Wenn du das kannst, ist der Rest nur noch die Umsetzung in der Sprache.

[__blackjack__]

SCNR

Code: Alles auswählen

#!/usr/bin/env python3
from more_itertools import collate

from attr import attrib, attrs


@attrs
class Node:
    item = attrib()
    next = attrib(default=None)


@attrs
class LinkedList:
    head = attrib(default=None)

    def __iter__(self):
        if self.head:
            node = self.head
            while node:
                yield node.item
                node = node.next

    @classmethod
    def from_iterable(cls, iterable):
        iterator = iter(iterable)
        result = LinkedList()
        try:
            first_item = next(iterator)
        except StopIteration:
            pass
        else:
            result.head = node = Node(first_item)
            for item in iterator:
                node.next = Node(item)
                node = node.next
        return result


def merge(iterable_a, iterable_b):
    return LinkedList.from_iterable(collate(iterable_a, iterable_b))


def main():
    list_a = LinkedList.from_iterable([1, 3, 5, 7])
    list_b = LinkedList.from_iterable([0, 2, 4, 6])
    print(list_a)
    print(list_b)
    print(merge(list_a, list_b))


if __name__ == "__main__":
    main()

[kbr]

Dank "itertools.chain" geht das auch als kurzer Einzeiler, was aber vermutlich nicht im Sinne der Übung ist und ich deshalb nicht abzugeben raten würde.

[Sirius3]

@DeaD_EyE: die Aufgabe setzt ja irgendeine Implementierung einer verketteten Liste voraus. Das sind dann 10 Zeilen, eine nicht ganz so gut lesbare Variante für beliebig viele Listen 6 Zeilen.

Mit passenden Routinen für die verkettete Liste, ist das ein Einzeiler:

Code: Alles auswählen

L3 = VerketteteListe.from_iterable(chain(*zip(L1, L2)))

Wobei hier wohl nicht die Listen L1 und L2 verändert werden (aber das war ja nur ein "dürfen").

[DeaD_EyE]

Die Elemente von L1 und L2 sollen nicht vor dem Einfügen sortiert werden?
Dann ist auf jeden Fall der Einzeiler in Ordnung.

Code: Alles auswählen

from itertools import chain


def merge(*iterables):
    yield from chain.from_iterable(zip(*iterables))

L1, L2, L3 =   range(0, 10, 3), range(1, 10, 3), range(2, 10, 3),
L4 = list(merge(L3, L2, L1))

Und falls die Elemente vorher sortiert werden sollen, bevor sie verkettet werden:

Code: Alles auswählen

def merge(*iterables):
    yield from chain.from_iterable(map(sorted, zip(*iterables)))

Wird dem OP aber wahrscheinlich nicht weiterhelfen, da er das auch erklären muss/soll.
Ich gehe davon aus, dass die Lerher/Professoren das Forum kennen.

[__deets__]

Die Listen sind sortiert. Sie sollen - wie bei merge sort - in eine immer noch sortierte Gesamtliste uebernommen werden. EInfdaches chaining tut's da nicht, da muss man schon Elementweise vergleichen & dann entscheiden, was man nimmt.

[kbr]

Ich hatte überlesen, dass es sich um einfach verkettete Listen handelt. Also keine builtin Python-Liste, sondern so was, wie __blackjack__ schon gezeigt hat:

Code: Alles auswählen

class Item:
    def __init__(self, value, next_item=None):
        self.value = value
        self.next_item = next_item

Dann heißt es im Sinne der Aufgabe wohl "Zeiger umbiegen" und der Hinweis, dass L1 bzw. L2 geändert werden dürfen, erschließt sich genauso, wie die lineare Laufzeit.

[__blackjack__]

Wobei meine Variante nichts spezifisches von der verketteten Liste verwendet sondern die einfach als ”iterable” ansieht und auch in linearer Zeit läuft. Nur das der Aufgabensteller `more_itertools.collate()` zu verwenden wahrscheinlich nicht akzeptieren wird. Das ist dabei genau der Teil der laut Aufgabe implementiert werden soll.

[kbr]

Wie ich gerade sehe, ist more_itertools.collated() deprecated zugunsten von heapq.merge() und aktuell auch nur noch ein Alias dafür.

@yzxyyy: heapq.merge() ist nicht die Lösung für die gestellte Aufgabe, bei der einfach verkettete Listen verwendet werden sollen.

[__blackjack__]

@kbr: Wenn die einfach verkettete Liste iterierbar ist und eine Möglichkeit bietet eine solche Liste aus einem „iterable“ zu erstellen, warum nicht? Lineare Zeit stimmt, und die Aufgabe sagt die ursprünglichen Listen *dürfen* verändert werden, nicht das sie verändert werden *müssen*.

[kbr]

@__blackjack__: Aus praktischer Sicht stimme ich dir zu, aber ich vermute, du setzt zu viel voraus. Hier soll mit Zeigern gearbeitet werden. Kann man auch mit Python nachempfinden. Das die idiomatische Nutzung der Sprache dabei nicht berücksichtigt wird, ist sicher unglücklich.