Suche Lösungsansatz

[normdew]

Hallo zusammen,

Ich habe eine Aufgabenstellung. Ich bin neu in Python und suche Lösungsansätze durch euer Einwerfen von Stichworten oder anderes vergleichbar umfangreiches Zutun. Mir ist klar, dass ich mich hier nicht hinstellen kann und von euch die Lösung aufgetischt bekommen werde. Klar ist mir auch, dass ich Python auch verstehen lernen muss und das geht denke ich aber eben am besten mit einem konkreten Problem.

Folgende Aufgabe ist es:

Es besteht eine konkrete Anzahl von 72 Objekten (prinzipiell gern aber auch beliebig erweiterbar, hat aber keine Priorität).
Alle Objekte sind miteinander in folgender Weise netzartig verkettet:
Jedes dieser Objekte hat mindestens 1, maximal 2 konkrete Nachfolger und genauso mindestens 1, maximal 2 konkrete Vorgänger. Jedes dieser Objekte hat außerdem einen konkreten eindeutigen Namen.

Folgende eine Netzstruktur ergibt sich, um sie mal optisch darzustellen (hoffe, dass man es erkennt):

Code: Alles auswählen

Meine Objekte sind die Kanten der Sechsecke!!
|                                  o-----o
|                                 /       \
|                          o-----o         o-----o
|                         /       \       /       \
|                  o-----o         o-----o         o-----o
|                 /       \       /       \       /       \
|                o         o-----o         o-----o         o
|                 \       /       \       /       \       /
|                  o-----o         o-----o         o-----o
|                 /       \       /       \       /       \
|                o         o-----o         o-----o         o
|                 \       /       \       /       \       /
|                  o-----o         o-----o         o-----o
|                 /       \       /       \       /       \
|                o         o-----o         o-----o         o
|                 \       /       \       /       \       /
|                  o-----o         o-----o         o-----o
|                         \       /       \       /
|                          o-----o         o-----o
|                                 \       /
|                                  o-----o

Wie man hoffentlich erkennt, könnten diese Objekte auch Kanten von Sechsecken sein.
So, eine Kette soll nun aus 5 dieser Objekte (Kanten der Sechsecke) bestehen (gern aber auch wieder beliebig mehr).

Ein Script soll sämtliche möglichen 5er-Ketten, die es geben kann ermitteln, zählen, ausgeben, what ever...

Mit OOP machts doch sicher am meisten Sinn oder?

Code: Alles auswählen

class Knoten:
    def __init__(self,i,name,avg,anf,vg1,vg2,nf1,nf2):
        self.i = i #laufende Nummer
        self.name = name
        self.avg = avg #avg = 'A'nzahl an 'V'or'g'ängern, min. 1, max. 2
        self.anf = anf #ang = 'A'nzahl an 'N'ach'f'olgern, min. 1, max. 2
        self.vg1 = vg1 
        self.vg2 = vg2
        self.nf1 = nf1 
        self.nf2 = nf2

Ist das soweit erstmal richtig?

[BlackJack]

@normdew: Die Namen sind furchtbar schlecht gewählt. Namen sollten dem Leser vermitteln was die Bedeutung des dahinter stehenden Objekts ist, möglichst ohne dass er sich dazu einen Kommentar durchlesen muss. Das geht nicht immer, aber in diesem Fall gibt es sicher bessere Namen. Abkürzen sollte man auch nur solange die Abkürzungen allgemein bekannt sind. `avg` ist eine übliche Abkürzung für `average` (deutsch: Durchschnitt). Der Name ist also doppelt ungünstig, nicht nur dass es ein Buchstabenkürzel ist — es bedeutet für einige Leser auch noch etwas anderes als eigentlich gemeint ist.

Durchnummerierte Namen sind oft ein Zeichen, dass man eigentlich eine Liste oder eine andere Datenstruktur verwenden wollte. Wenn Du in diesem Falle die Vorgänger und Nachfolger jeweils in einer Liste speicherst, dann brauchst Du die Information wie viele es davon gibt, nicht mehr explizit speichern.

[normdew]

Danke das ist schon mal die erste wichtige Lektion für mich. Ich verfalle oft in diese Schreibfaulheit. Also gut, lieber Variablen wählen, die schnell erkennbar sind ohne sie erst übersetzen zu müssen.

[normdew]

Durchnummerierte Namen sind oft ein Zeichen, dass man eigentlich eine Liste oder eine andere Datenstruktur verwenden wollte. Wenn Du in diesem Falle die Vorgänger und Nachfolger jeweils in einer Liste speicherst, dann brauchst Du die Information wie viele es davon gibt, nicht mehr explizit speichern.

Benötige ich Klassen Vorgänger und Nachfolger?

Wie muss ich das verstehen: Listen? Die Liste Vorgänger ist doch letztendlich identisch mit der Liste Nachfolger, denn jedes Objekt ist doch selbst auch irgendein Vorgänger oder Nachfolger?

Code: Alles auswählen

vorgaenger = ['Objekt1', 'Objekt2', '...' , 'Objekt72']
nachfolger = ['Objekt1', 'Objekt2', '...' , 'Objekt72']

Klar ist mir, dass ich Listen brauche, damit ich jedes Element der Liste ansprechen kann. Tschuldigung, wenn ich mich nicht immer ganz richtig ausdrücke.

[derdon]

So wie ich das in deiner Abbildung sehe, sind für die obersten Punkte keine Eltern da und für die untersten keine Kinder. Du sprichst aber immer von "mindestens 1". Übersehe ich da etwas?

[normdew]

So wie ich das in deiner Abbildung sehe, sind für die obersten Punkte keine Eltern da und für die untersten keine Kinder. Du sprichst aber immer von "mindestens 1". Übersehe ich da etwas?

So wie ich deine Herangehensweise verstehe mein ich es aber nicht. Das Netz ist nicht hierarchich von oben nach unten abzuarbeiten, so dass - wie du schon sagst - plötzlich unten keine Kinder mehr da sind. War vielleicht einfach schlecht von mir "gemalt" ;o)

Code: Alles auswählen

jetzt haben die kleinen o's keine Bedeutung mehr; die Objekte sind die gestrichelten Kanten des Sechsecks!!
|                  o-----o
|                 /       \
|                o         o
|                 \       /
|                  o-----o     

Wenn ich diese vereinfachte Struktur mal nehme:
Jedes Objekt (die Kanten des Sechsecks) hat eine Verbindung zur nächsten und vorhergehenden Kante. Jedes Objekt hat hier genau einen Vorgänger und genau einen Nachfolger.

Hab das mal oben angepasst!

[derdon]

Ah, dann passen die Wörter "Vorgänger" und "Nachfolger" also auch nicht so gut. Habe dabei nämlich in Gedanken an einen Baum gedacht. Also gibt es keine Hierarchien und man sollte eher von "Nachbarn" sprechen. Also beinhaltet jeder Knoten als Eigenschaft eine Liste von Nachbarn (was einer Liste von Knoten-Instanzen entspricht). Stimmst du mir soweit zu?

[normdew]

man sollte eher von "Nachbarn" sprechen. Also beinhaltet jeder Knoten als Eigenschaft eine Liste von Nachbarn (was einer Liste von Knoten-Instanzen entspricht). Stimmst du mir soweit zu?

Alles klar, ja, dem kann ich folgen!

[normdew]

macht man das dann so?

Code: Alles auswählen

class kante:
  def __init__(self):                                      
    self.name = ...
    self.anzahl_nachbarn = ...
  
  def nachbarn(...):
    kante.nachbarn = ['kante1', 'kante2', 'kante3', 'kante4', 'kante5']
...

[pillmuncher]

Ich empfehle zur Lektüre dies hier:

• The Zen of Python
• Den Python Style Guide
• Das Tutorial
• Die Doku zur Standard-Lib

Desweiteren sehe ich bei deinem Entwurf das Problem, dass, wenn ein Knoten erzeugt wird, dieser andere Knoten übergeben bekommt, die, wenn sie erzeugt werden, andere Knoten übergeben bokommen, die, wenn sie erzeugt werden, andere Knoten... - folglich musst du den Aufbau des Graphen von der Erzeugung der Knoten trennen und das ganze in zwei Schritten erledigen, statt in Knoten.__init__(). Gemäß deinen Ausführungen sind Vorgänger und Nachfolger relative Begriffe. Fass doch einfach beides, wie schon von derdon vorgeschlagen, zu Nachbarn zusammen. Außerdem würde ich den Graphen als eigenständige Datenstruktur programmieren, statt dass jeder Knoten seinen Platz im Graphen bzw. seine Nachbarn kennen muss:

Code: Alles auswählen

from collections import defaultdict

class Node(object):
    def __init__(self, nr):
        self.nr = nr
    def __repr__(self):
        return 'Node(%d)' % self.nr

graph = defaultdict(set)

def add_neighbours(node, *neighbours):
    for each in neighbours:
        graph[each.nr].add(node)
        graph[node.nr].add(each)

nodes = [Node(i) for i in xrange(72)]

add_neighbours(nodes[0], nodes[6])
add_neighbours(nodes[1], nodes[7])
add_neighbours(nodes[2], nodes[7])
add_neighbours(nodes[3], nodes[8])
add_neighbours(nodes[4], nodes[8])
add_neighbours(nodes[5], nodes[9])
add_neighbours(nodes[6], nodes[10], nodes[11])
add_neighbours(nodes[7], nodes[12], nodes[13])
add_neighbours(nodes[8], nodes[14], nodes[15])
add_neighbours(nodes[9], nodes[16], nodes[17])
add_neighbours(nodes[10], nodes[18])
add_neighbours(nodes[11], nodes[19])
add_neighbours(nodes[12], nodes[19])
# usw.


def paths(node, n):
    """ generiere alle Pfade zu allen Knoten, die in genau
        n Schritten von node aus erreicht werden können """

for path in paths(nodes[7], 5):
    print path

paths() musst du als Backtracker programmieren. Am einfachsten geht das als Generator Function.

[normdew]

Danke für deine umfangreiche Antwort.

Wie gesagt, als Neuling, werde ich mich jetzt erstmal daran machen, deine Antwort überhaupt zu verstehen und den Code-Schnipsel nachzuvollziehen.
Deshalb bleiben weitere Schlussfolgerungen und Antworten meinerseits gerade aus.

paths() musst du als Backtracker programmieren. Am einfachsten geht das als Generator Function.

Ah Backtracking nennt man das Prinzip, Danke, großartig, danach hab ich gesucht!

[normdew]

@pillmuncher: So, wie schon gezeigt: jetzt steh ich bei yield(). ... puh
Momentan ist das alles für mich ein großes Puzzle: überall liegen die Teile und ich erkenne, das sie irgendwie auch zum Bild gehören, weiß nur noch nicht, wie ich sie zusammensetze.

return() ist eine Ausgabefunktion ohne "Gedächtnis", yield() dagegen ein funktionsähnlicher Generator mit "Gedächtnis". Ist das richtig?

Hab ein bischen zu tun:

• Generatoren (python-kurs.eu)
• Generatoren (openbook.galileocomputing.de)

[BlackJack]

@normdew: Beides sind keine Funktionen, sondern Anweisungen die den Kontrollfluss beeinflussen. ``return`` beendet den Kontrollfluss in einer Funktion und ``yield`` setzt ihn nur aus bis das nächste Element von dem Generator angefordert wird.

[pillmuncher]

@normdew: Hier ein etwas einfacheres Beispiel, wie man Backtracker mittels Generatoren baut. Dabei geht es darum, in einem Baum alle Pfade von einem beliebigen Knoten zu allen darunterliegenden Blättern zu finden:

Code: Alles auswählen

Mein Freund, der Baum:

          0
         / \
        /   \
       /     \
      1       2
     / \     / \
    3   4   5   6
   /   / \
  7   8   9

Code: Alles auswählen

tree = defaultdict(list)

nodes = [Node(i) for i in xrange(10)]

tree[nodes[0]].append(nodes[1])
tree[nodes[0]].append(nodes[2])
tree[nodes[1]].append(nodes[3])
tree[nodes[1]].append(nodes[4])
tree[nodes[2]].append(nodes[5])
tree[nodes[2]].append(nodes[6])
tree[nodes[3]].append(nodes[7])
tree[nodes[4]].append(nodes[8])
tree[nodes[4]].append(nodes[9])


def branches(node, branch=[]):
    if node in tree:
        for child in tree[node]:
            for each in branches(child, branch + [node]):
                yield each
    else:
        yield branch + [node]

for branch in branches(nodes[1]):
    print branch

Ergebnis:

Code: Alles auswählen

[Node(1), Node(3), Node(7)]
[Node(1), Node(4), Node(8)]
[Node(1), Node(4), Node(9)]

[normdew]

Mal so ganz nebenbei eine Frage außerhalb ... Woran kann es liegen, dass meine Python Shell xrange nicht kennt (NameError: name 'xrange' is not defined)?

[Hyperion]

Mal so ganz nebenbei eine Frage außerhalb ... Woran kann es liegen, dass meine Python Shell xrange nicht kennt (NameError: name 'xrange' is not defined)?

Du nutzt vermutlich Python3

Py2: range -> liste, xrange -> generator

Py3: range -> generator, xrange gibbet nicht mehr.

[cofi]

Daran dass man Python 3 (dann nimm `range`) oder ein uraltes Python nutzt (ich glaube xrange kam in Python 2.3 dazu -- dann solltest du schleunigst updaten)

[normdew]

Mal so ganz nebenbei eine Frage außerhalb ... Woran kann es liegen, dass meine Python Shell xrange nicht kennt (NameError: name 'xrange' is not defined)?

Du nutzt vermutlich Python3

Py2: range -> liste, xrange -> generator

Py3: range -> generator, xrange gibbet nicht mehr.

hab Py3 Danke für die Aufklärung; dann brauch ich mir keine Sorgen machen das ich irgendein feature verliere wenn ich "nur" range nehme.

[CM]

edit: gelöscht, da Teil des Threads übersehen - sorry.