[GO] Lösen Sie einen Strich (Backtrack ohne Rekursion in Python)

One-Stroke-Schreiben ist schmelzig!

Es ist eine berühmte Geschichte. Das Schreiben mit einem Strich ist eine sehr einfache Regel, mit der Sie beurteilen können, ob Sie eine Lösung finden können oder nicht. Das sogenannte Ölerdiagramm.

1. Muss ein verketteter Graph sein. Das heißt, es ist eine Gruppe. (Sie können die Kanji-Zeiten nicht mit einem Strich schreiben. Es gibt keine Seite, die das äußere und das innere Quadrat verbindet, also können Sie nicht Ihr Bestes geben.)
2. Muss eine der folgenden sein. 2-1: Jeder Punkt hat eine gerade Anzahl von Seiten (in diesem Fall können Sie von jedem Punkt aus beginnen und schließlich zum Startpunkt zurückkehren). 2-2: Nur zwei Punkte haben eine ungerade Anzahl von Seiten, und die anderen Punkte haben eine gerade Anzahl von Seiten. (In diesem Fall ist der Punkt mit der ungeraden Anzahl von Seiten der Startpunkt und der Punkt mit der anderen ungeraden Seite der Endpunkt.)

...... Wenn es sich nicht um ein großes One-Stroke-Schreiben handelt, können Sie es anscheinend lösen, indem Sie den Startpunkt festlegen und richtig zurückverfolgen, ohne an irgendetwas zu denken.

Die Option, nicht wiederkehrend

Dann sollte ich anfangen zu schreiben. Als ich versuchte, eine rekursive Funktion zu erstellen, fand ich das ärgerlich. Der zurückgegebene Wert sollte eine Liste der Reihenfolge sein, in der die Zeile befolgt werden soll. Erstellen Sie jedes Mal eine neue Liste, wenn Sie eine rekursive Funktion aufrufen? Gibt die rekursive Funktion eine Liste der Länge 1 zurück und verlängert die Liste jedes Mal, wenn sie einen Wert zurückgibt? Als ich darüber nachdachte, dachte ich, ich sollte meinen eigenen Stapel haben und ihn in einer Schleife drehen.

Schieben Sie den Iterator in den Stapel

Wie wäre es dann mit einem Aufruf einer rekursiven Funktion in der Mitte der Schleife? Ist es möglich, von der Mitte fortzufahren? es kann. Wenn Sie das Iteratorobjekt verlassen, beginnt die Schleife mit der nächsten.

Mit einer for-Schleife ist es nicht möglich, den Iterator in der Mitte zu ersetzen (es ist möglicherweise möglich, aber ich weiß nicht, wie es geht) Ich habe versucht, das Element aus dem Iterator zu extrahieren, während ich die while-Schleife verwendet habe.

Als Grundwissen in Python

for x in iterable:
    foo(x)

Ist ungefähr gleichbedeutend mit:

_it = iter(iterable)
while 1:
    try:
        x = next(_it)  # Python3
        # x = _it.next()  # Python2
    except StopIteration:
        break
    else:
        foo(x)

Kurz gesagt, der Iterator gibt das nächste Element zurück, wenn er next aufruft, und löst eine StopIteration-Ausnahme aus, wenn kein nächstes Element vorhanden ist. Die for-Schleife ruft als nächstes hinter den Kulissen auf und beendet die Schleife, wenn Stop Iteration kommt.

One-Stroke-Code

Infolgedessen konnte ich so etwas tun.

from collections import Counter

# Edges := [Edge*]
# Edge := (Vertex, Vertex)
# Vertex := Hashable except None

def solve_hitofude(edges):
    def _make_vertexcounter(edges):
        'Zählen Sie die Anzahl der Seiten für jeden Scheitelpunkt'
        c = Counter()
        for x, y in edges:
            c[x] += 1
            c[y] += 1
        return c

    def _make_edgeflag(edges, value=True):
        'Erstellen Sie ein Wörterbuch, um die Seite zu verwalten, die Sie übergeben haben'
        d = dict()
        for edge in edges:
            d[edge] = value
        return d

    def _get_head_tail(counter):
        'Bestimmen Sie den Start- und Endpunkt'
        odd = []
        for k,v in counter.items():
            if v&1: odd.append(k)
        if len(odd) == 2:
            return tuple(odd)
        elif len(odd) == 0:
            t = c.most_common(1)[0][0]
            return t, t
        else:
            return None, None

    def _edge_selector(pos, edgeflag):
        'Generatorfunktion. Erstellen Sie einen Generator, der Seiten liefert, die mit einem bestimmten Punkt verbunden sind und noch nicht bestanden haben.'
        for edge in edgeflag:
            if edgeflag[edge]:
                a, b = edge
                if a == pos:
                    yield edge, b
                if edgeflag[edge] and b == pos:
                    yield edge, a

    stack_pos = []  #Ordnen Sie die Punkte, die Sie bestanden haben, an
    stack_edge = []  #Ich werde in die Seite setzen, die vergangen ist
    stack_selector = []  # _edge_Setzen Sie den Wählgenerator ein

    c = _make_vertexcounter(edges)
    remain = _make_edgeflag(edges)

    pos, tail = _get_head_tail(c)
    if pos is None:
        return None
    n = len(edges)
    selector = _edge_selector(pos, remain)

    while n:  #Wenn Sie allen Seiten folgen, sind Sie fertig
        try:
            edge, nextpos = next(selector)
        except StopIteration:  #Rückkehr, wenn keine rückverfolgbaren Seiten mehr vorhanden sind. Wenn es nicht mehr zurückgeben kann, gibt es None zurück.
            if stack_pos:
                pos = stack_pos.pop()
                remain[stack_edge.pop()] = True
                selector = stack_selector.pop()
                n += 1
            else:
                return None
        else:  #Verarbeitung, wenn sie zurückverfolgt werden kann.
            stack_pos.append(pos)
            stack_edge.append(edge)
            stack_selector.append(selector)
            pos = nextpos
            remain[edge] = False
            selector = _edge_selector(pos, remain)
            n -= 1
    if pos == tail:
        return stack_pos, stack_edge
    assert False

Jedes Mal, wenn ich einer Seite folge / zurückkehre, wird die Auswahlvariable, die ein Iterator ist, ausgetauscht.

Lass es uns versuchen

Ich habe versucht, es mit PyQt4 in eine GUI zu verwandeln. (Es hätte knusprig sein sollen, aber es ist ein Geheimnis, dass es viel Zeit gekostet hat, sich auf verschiedene Dinge einzulassen. Ich würde gerne bald einen Artikel über Qt / PyQt schreiben.)

Der gesamte Code ist öffentlich auf Github.