Datenstruktur "Baum"

[mr_egbert]

Hallo zusammen,

aus Spaß an der Freude wollte ich das MIU-System aus dem Buch Gödel, Escher, Bach programmieren. Das Erzeugen neuer Sätze konnte ich lösen (s.u.). Jetzt brauche ich eine Datenstruktur "Baum" und eine Möglichkeit diesen Baum auszugeben. Gibt es dafür ein geeignetes Modul?

Die Regeln für das MIU-System sind wie folgt:
Der erste Satz, von dem alle anderen abgeleitetet werden ist "MI". Es gibt vier Regeln nach denen ein Satz weiterentwickelt werden kann:

• Wenn ein Satz mit "I" endet, dann darf "U" angehängt werden.
• Aus Mx darf Mxx werden.
• "III" darf durch "U" ersetzt werden.
• "UU" darf gestrichen werden.

(Die Frage, die in dem Buch aufgeworfen wird ist übrigens, ob "MU" erzeugt werden kann.)

Das Erzeugen aller möglichen Sätze, die aus einem Satz erzeugt werden können habe ich wie folgt gelöst:

Code: Alles auswählen

def derive_terms(term):
    terms = []
    if term[-1]=="I":
        terms.append  (term + "U")
    terms.append (term + term[1:])
    for _ in range(len(term)):
        try:
            position = term.index("III",_)
            derived_term = term[:position] + "U" + term[position+3:]
            if not derived_term in terms:
                terms.append (derived_term)
        except ValueError:
            continue
    for _ in range(len(term)):
        try:
            position = term.index("UU",_)
            derived_term = term[:position] + term[position+2:]
            if not derived_term in terms:
                terms.append (derived_term)
        except ValueError:
            continue   
    return terms

[rogerb]

Hallo mr_egbert,

Jetzt brauche ich eine Datenstruktur "Baum" und eine Möglichkeit diesen Baum auszugeben. Gibt es dafür ein geeignetes Modul?

Das sieht vielversprechend aus:
https://anytree.readthedocs.io/en/latest/#

Man kann z.B. einen dictionary importieren und dann graphisch als Bild ausgeben.


Ich verstehe nicht was du mit 'darf' ausdrücken willst:

Wenn ein Satz mit "I" endet, dann darf "U" angehängt werden.
Aus Mx darf Mxx werden.
"III" darf durch "U" ersetzt werden.
"UU" darf gestrichen werden.

Meinst du 'soll' ?

[__blackjack__]

@mr_egbert: Was sollte denn so ein Modul anbieten was so allgemein ist, das man es nicht selber programmieren müsste für den speziellen Anwendungsfall?

Ganz allgemein für Graphen, und damit auch Bäume, und Algorithmen darauf, gibt es `networkx`.

Die beiden ``for``-Schleifen sehen sehr ähnlich aus, da könnte man sicher Gemeinsamkeiten herausziehen.

Aber die sehen auch sehr ineffizient aus. Warum wird da von jeder Position ausgehend per `index()` gesucht? Das findet doch auf der einen Seite die gleichen Treffer mehrfach. Auf der anderen Seite wird `index()` für jede Position aufgerufen, auch wenn die gesuchte Zeichenkette überhaupt nicht vorkommt‽ Beides macht keinen Sinn.

Wenn man sich den Test vor dem hinzufügen anschaut, sieht das aus als wäre `terms` besser ein `set` statt einer Liste.

Die Regel mit dem "M" kommt in dem Code gar nicht vor‽

Aber selbst ohne die Regel, bin ich mir recht sicher, das nicht alle Ableitungen erzeugt werden.

@rogerb: Mit „darf“ ist gemeint, die Regel kann angewendet werden, muss aber nicht.

[mr_egbert]

Vielen Dank für die Antworten. Jetzt kann ich erstmal selber weiter tüfteln.

@rogerb
Auf anytree bin ich beim googeln schon gestoßen. Für mich ist es nur schwer einzuschätzen, ob ein bestimmtes Modul auf meinen Anwendungsfall passt, ob es gängig ist oder ehrer exotisch. Danke für den Tip, vor allem die Ausgabe als Bild ist schick.

@__blackjack__
Von networkx habe ich noch nie gehört, das werde ich mir merken. Von Graphen habe ich eine erste ungefähre Vorstellung.

Was sollte denn so ein Modul anbieten was so allgemein ist, das man es nicht selber programmieren müsste für den speziellen Anwendungsfall?

Es geht a) ums Befüllen der Datenstruktur und b) ums Ausgeben. Zunächst muss ich mir glaube ich klar werden, wie und in welcher Reihenfolge ich mich (vermutlich durch rekusives Aufrufen der Funktion) durch den Baum bewege, womit ich die Frage nach einem Modul jetzt erstmal hinten anstelle.
Vielen Dank für den Hinweis.

Für M gibt es keine Regel. Der Satz MI ist gegeben (Axiom) alle anderen müssen davon abgeleitet werden, die Sätze beginnen also immer mit M. Dieses System ist sinnlos (nicht bedeutungstragend?) und dient nur als Einstieg in das Thema formale Systeme.

Mit der Komstruktion der Schleifen will ich folgenden Fall abdecken:
MIUIIIIIU -> MIUUIIU
MIUIIIIIU -> MIUIIUU
Wobei das im Fall von UU zugegeben sinnlos ist.

[__blackjack__]

@mr_egbert: Ich dachte Punkt 2 Mx → Mxx wäre eine Regel, weil es in der Aufzählung der Regeln steht.

[rogerb]

@mr_egbert,

müsste es nicht noch einen dritten Fall geben?:
MIUIIIIIU -> MIUIUIU

[mr_egbert]

Ich möchte gerne zur Erklärung diesen Link nachreichen: http://www.brunnenrand.de/projekte/math ... aetsel.htm
Die Seite habe ich gestern erst gefunden, sonst hätte ich sie gleich mit angegeben.

@rogerb:
Ich weiß nicht, ob MIUIIIIIU ein Satz im Sinne des Systems ist, weil ich nicht weiß, ob er sich von MI aus erzeugen lässt. Davon abgesehen ließen sich die Regeln wie folgt anwenden:

• Regel 1: Falls der Satz mit I endet, darf U angehängt werden. => Kann auf MIUIIIIIU nicht angewendet werden.
• Regel 2: Aus Mx darf Mxx (beachte, x ist kursiv und steht für eine Zeichenkette) werden => Aus MIUIIIIIU wird MIUIIIIIUIUIIIIIU
• Regel 3: "III" darf durch "U" ersetzt werden. => Das geht m. E. auf zwei Arten, aus MIUIIIIIU wird MIUUIIU oder MIUIIUU
• Regel 4: "UU" darf gestrichen werden. => Kann auf MIUIIIIIU nicht angewendet werden.

Ich sehe nicht, nach welcher Regel aus MIUIIIIIU -> MIUIUIU wird.

[mr_egbert]

Hier noch der verbesserte Code:

Code: Alles auswählen

def derive_terms(term):
    terms = []
    #rule 1: If term ends with 'I' you may append 'U'
    if term[-1]=="I":
        terms.append(term + "U")
    #rule 2: You may repeat all characters that follow the preceding 'M'
    terms.append(term + term[1:])
    #rule 3: You may replace "III" with "U"
    for _ in range(len(term)):
        try:
            position = term.index("III",_)
            derived_term = term[:position] + "U" + term[position+3:]
            if not derived_term in terms:
                terms.append(derived_term)
        except ValueError:
            continue
    #rule 4: You may delete "UU"
    if term.find("UU")>0:
        position=term.find("UU")
        terms.append(term[:position]+term[position+2:])   
    return terms

Den Hinweis mit 'set' zu arbeiten habe ich noch nicht umgesetzt, weil mir der Vorteil noch nicht klar ist.

[Sirius3]

Wenn man prüft, ob ein String mit einem Substring endet, dann benutzt man endswith.
`_` zeigt an, dass diese Variable nicht verwendet wird, Du benutzt aber _ innerhalb der for-Schleife.
Es ist sehr umständlich, per index von jeder Position ab zu suchen, wenn Du schon weißt, dass III erst an Position `position` auftaucht.
`continue` sollte man sehr sparsam nutzen, hier reicht ein einfaches `pass`.
Mal benutzt Du index, mal find (und das sogar zwei mal, für das selbe Ergebnis). Warum?

Code: Alles auswählen

def derive_terms(term):
    terms = []
    #rule 1: If term ends with 'I' you may append 'U'
    if term.endswith("I"):
        terms.append(term + "U")
    #rule 2: You may repeat all characters that follow the preceding 'M'
    terms.append(term + term[1:])
    #rule 3: You may replace "III" with "U"
    position = 0
    while True:
        position = term.find("III", position)
        if position < 0:
            break
        derived_term = term[:position] + "U" + term[position + 3:]
        if derived_term not in terms:
            terms.append(derived_term)
        position += 1
    #rule 4: You may delete "UU"
    position = term.find("UU")
    if position >= 0:
        terms.append(term[:position] + term[position + 2:])
    return terms

[mr_egbert]

@Sirius3: Vielen Dank für die Verbesserungen.

[mr_egbert]

Meine Lösung:

Code: Alles auswählen

CALCULATION_DEPTHS = 3


class Term:

    def __init__(self, term, parents):
        self.term = term
        self.parents = parents
        self.childs = []
        print(self.term, self.parents)
        if len(self.parents) < CALCULATION_DEPTHS:
            self.create_childs()

    def create_childs(self):
        # rule 1: If term ends with 'I' you may append 'U'
        if self.term.endswith("I"):
            self.childs.append(Term(self.term + "U", self.parents + [self.term]))
        # rule 2: You may repeat all characters that follow the preceding 'M'
        self.childs.append(Term(self.term + self.term[1:], self.parents + [self.term]))
        # rule 3: You may replace "III" with "U"
        position = 0
        while True:
            position = self.term.find("III", position)
            if position < 0:
                break
            derived_term = self.term[:position] + "U" + self.term[position + 3:]
            if derived_term not in self.childs:
                self.childs.append(Term(derived_term, self.parents + [self.term]))
            position += 1
        # rule 4: You may delete "UU"
        position = self.term.find("UU")
        if position >= 0:
            self.childs.append(Term(self.term[:position] + self.term[position + 2:], self.parents + [self.term]))


def main():
    Term("MI", [])


if __name__ == '__main__':
    main()

[__blackjack__]

@mr_egbert: Bei einem `set` brauchst Du nicht testen ob das Ergebnis schon enthalten ist, und das geht da effizienter.

Den Sinn von der Klasse verstehe ich jetzt nicht so ganz, die macht das ja eigentlich nur komplizierter und produziert mehr Daten. Werden die denn gebraucht? Also musst Du wissen in welchem Schritt welche Terme existieren und selbst wenn, muss das unbedingt in einer Klasse mit nur einer Methode neben der `__init__()` stecken, die zu dem noch eigentlich nur ein ausgelagerter Teil der `__init__()` ist und keine Methode die man sinnvoll aufrufen kann, nach dem das Objekt erstellt wurde?

Was in der Regel auch ein Alarmzeichen ist, ist wenn das Attribut was den Wert des Typs festlegt, den gleichen Namen trägt wie der Typ. Das heisst in diesem Fall ja das ein Term aus einem Term besteht. Das klingt doch komisch. Hier wird der Knoten eines Baumes und der Wert von dem Knoten komisch vermischt.

Der ``in``-Test ist falsch, weil das Suchen einer Zeichenkette in einer Liste mit `Term`-Objekten hier *immer* `False` liefern wird, weil keine Zeichenkette gleich eines `Term`-Objektes ist.

Mehrzahl von „child“ ist „children“. „childs“ gibt es nicht.

[rogerb]

@mr_egbert,

Danke für den Link, interessantest Thema.

Ich sehe nicht, nach welcher Regel aus MIUIIIIIU -> MIUIUIU wird.

REGEL III: Wenn in einer der Ketten Ihrer Sammlung III vorkommt, können Sie eine neue Kette mit U anstelle von III bilden.

MIU - III - IIU ---> MIU - U - IIU
MIUI - III - IU ---> MIUI - U - IU
MIUII - III - U ---> MIUII - U - U

Aus den 5 IIIII kann man ja drei Gruppierungen von je 3 III ziehen. Also, so verstehe ich die Regel jedenfalls

[__blackjack__]

@mr_egbert: Die Interpretation von rogerb von Regel 3 ist in der verlinkten Webseite auch in einem Beispiel: „Aus MIIII können Sie MIU (oder auch MUI) machen.“

[mr_egbert]

@__blackjack__
1) set: OK, verstanden
2) Sinn von der Klasse
Es stimmt, die Klasse produziert viele Daten und ist für eine ernsthafte Anwendung ungeeignet. Auch die Ausgabe mit print ist ziemlich willkürlich. Mir ging es nur darum, dass ich damit einige Sätze produzieren kann, um einen Eindruck zu gewinnen, wie sich das System verhält. Insofern ist das Ergebnis für mich zufriedenstellend.
3) Alarmzeichen
Ja das klingt seltsam, ich fand den Ansatz aber praktisch und mir ist nix besseres eingefallen.
4) 'in'-Test
Ja, das funktioniert so leider nicht.
5) Childs -> Children
Hört sich so irgendwie auch besser an.

@__blackjack__
@rogerb
Ihr habt recht: MIUI - III - IU ---> MIUI - U - IU das entspricht den Regeln

Nochmal Danke.

[__blackjack__]

@mr_egbert: Noch mal bezüglich der Klasse: Für das was die macht, braucht man halt keine Klasse, das ist einfach nur unnötig kompliziert.

Die einzige nicht-magische Methode ist einfach nur ein Teil Code, der aus der `__init__()` ausgelagert wurde. Den kann man da problemlos wieder rein ziehen. Und dann hat man eine Klasse die nur aus einer `__init__()` besteht und von der der Code der das erste Exemplar erzeugt überhaupt gar keinen weiteren gebrauch macht. Das heisst man kann die Klasse mit der `__init__()` ganz einfach zu einer Funktion machen, weil es das letztendlich ist, was dieses Konstrukt beschreibt.

Was auch komisch ist, ist das `childs`/`children` nirgends benutzt wird. Diese Klasse ist ein wirklich komisches Konstrukt.

Übrigens kann man sich auch fragen ob ein Baum überhaupt passend ist, denn die Sätze können sowohl länger als auch kürzer werden, dass heisst es kann auch sein, dass man wieder zu bereits vorher generierten Worten zurückkehren könnte. Das wäre dann ein Graph.

[rogerb]

Hallo mr_egbert,

Danke nochmal für die Inspiration!
Ich habs auch mal versucht.
(An der Baumstruktur muss ich wohl noch arbeiten)

Code: Alles auswählen

"""
REGEL I: Wenn Sie eine Kette besitzen, deren letzter Buchstabe I ist, können Sie am Schluss ein U zufügen.
REGEL II: Angenommen Sie haben Mx Dann können Sie Ihrer Sammlung Mxx zufügen.
REGEL III: Wenn in einer der Ketten Ihrer Sammlung III vorkommt, können Sie eine neue Kette mit U anstelle von III bilden.
REGEL IV: Wenn UU in einer Ihrer Ketten vorkommt, kann man es streichen.
"""
import re


def build_chain(chain, depth_level):

    if depth_level > 4:
        return

    # apply rule 1
    if chain.endswith("I"):
        build_chain(chain + "U", depth_level + 1)

    # apply rule 2
    build_chain(chain + chain[1:], depth_level + 1)

    # apply rule 3
    iii_start_positions = [start_pos.start() for start_pos in re.finditer("(?=III)", chain)]

    for iii_start_position in iii_start_positions:
        build_chain(chain[:iii_start_position] + "U" + chain[iii_start_position + 3 :], depth_level + 1)

    # apply rule 4
    uu_start_positions = [start_pos.start() for start_pos in re.finditer("(?=UU)", chain)]
    for uu_start_position in uu_start_positions:
        build_chain(chain[:uu_start_position] + chain[uu_start_position + 2 :], depth_level + 1)

    print("-" * depth_level + chain)


build_chain("MI", 0)

----MIUIUIUIUIUIUIUIU
---MIUIUIUIU
--MIUIU
-MIU
----MIIUIIUIIUIIU
---MIIUIIU
--MIIU
----MIIIIUIIIIU
----MUIU
----MIUU
---MIIIIU
----MIIIIIIIIU
----MIIIIIIIIIIIIIIII
----MUIIIII
----MIUIIII
----MIIUIII
----MIIIUII
----MIIIIUI
----MIIIIIU
---MIIIIIIII
----MUIU
----MUIUI
---MUI
----MIUIU
---MIU
--MIIII
-MII
MI

[rogerb]

Hier das ganze mit anytree und verbesserter Ausgabe:

Code: Alles auswählen

"""
REGEL I: Wenn Sie eine Kette besitzen, deren letzter Buchstabe I ist, können Sie am Schluss ein U zufügen.
REGEL II: Angenommen Sie haben Mx Dann können Sie Ihrer Sammlung Mxx zufügen.
REGEL III: Wenn in einer der Ketten Ihrer Sammlung III vorkommt, können Sie eine neue Kette mit U anstelle von III bilden.
REGEL IV: Wenn UU in einer Ihrer Ketten vorkommt, kann man es streichen.
"""
import re
from anytree import Node, RenderTree


class ChainBuilder:
    def __call__(self, max_depth_level):
        self.max_depth_level = max_depth_level
        node = Node("MI")
        self.build_tree(node, 1)
        return node

    def build_tree(self, node, depth):
        if depth > self.max_depth_level:
            return

        self.find_children(node)
        for child in node.children:
            self.build_tree(child, depth + 1)

    def find_children(self, node):
        # apply rule 1
        if node.name.endswith("I"):
            Node(node.name + "U", parent=node)

        # apply rule 2
        Node(node.name + node.name[1:], parent=node)

        # apply rule 3
        iii_start_positions = [start_pos.start() for start_pos in re.finditer("(?=III)", node.name)]

        for iii_start_position in iii_start_positions:
            Node(node.name[:iii_start_position] + "U" + node.name[iii_start_position + 3 :], parent=node)

        # apply rule 4
        uu_start_positions = [start_pos.start() for start_pos in re.finditer("(?=UU)", node.name)]
        for uu_start_position in uu_start_positions:
            Node(node.name[:uu_start_position] + node.name[uu_start_position + 2 :], parent=node)


chain_builder = ChainBuilder()


for pre, _, node in RenderTree(chain_builder(4)):
    print(f"{pre}{node.name}")

Code: Alles auswählen

MI
├── MIU
│   └── MIUIU
│       └── MIUIUIUIU
│           └── MIUIUIUIUIUIUIUIU
└── MII
    ├── MIIU
    │   └── MIIUIIU
    │       └── MIIUIIUIIUIIU
    └── MIIII
        ├── MIIIIU
        │   ├── MIIIIUIIIIU
        │   ├── MUIU
        │   └── MIUU
        ├── MIIIIIIII
        │   ├── MIIIIIIIIU
        │   ├── MIIIIIIIIIIIIIIII
        │   ├── MUIIIII
        │   ├── MIUIIII
        │   ├── MIIUIII
        │   ├── MIIIUII
        │   ├── MIIIIUI
        │   └── MIIIIIU
        ├── MUI
        │   ├── MUIU
        │   └── MUIUI
        └── MIU
            └── MIUIU

[Sirius3]

@rogerb: eine Klasse ohne __init__ sieht immer etwas komisch aus. Hier könnte man statt __call__ auch einfach __init__ benutzen. Aber wenn man etwas tiefer schaut, dann merk man, dass `find_children` self gar nicht benutzt, also nicht Teil der Klasse sein muß. `build_tree` benutzt nur self.max_depth_level, so dass man statt self auch einfach max_depth_level übergeben könnte.

Code: Alles auswählen

def build_tree(max_depth_level):
    node = Node("MI")
    build_sub_tree(node, max_depth_level)
    return node

def build_sub_tree(node, depth):
    if depth <= 0:
        return

    find_children(node)
    for child in node.children:
        build_sub_tree(child, depth - 1)

def find_children(node):
    # apply rule 1
    replace_all(node, "I$", "IU")

    # apply rule 2
    Node(node.name + node.name[1:], parent=node)

    # apply rule 3
    replace_all(node, "III", "U")

    # apply rule 4
    replace_all(node, "UU", "")

def replace_all(node, old, new):
    start_positions = (match.start() for match in re.finditer(f"(?={old})", node.name))
    for start_position in start_positions:
        Node(node.name[:start_position] + new + node.name[start_position + len(old) :], parent=node)

[rogerb]

@Sirius3, ja, gute Verbesserungen. Ich hatte verschiedene Ansätze versucht und die Klasse war dann nicht mehr nötig. Die vielen anderen kleinen, aber feinen Verbesserungen sind mir auch aufgefallen! Werde ich aber vielleicht in einem separaten Thread aufgreifen.