Tree sortieren

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
cullmann
User
Beiträge: 13
Registriert: Donnerstag 10. April 2008, 19:08
Wohnort: Dublin

Tree sortieren

Beitragvon cullmann » Montag 21. April 2008, 00:01

Servus alle zusammen,

mir hat nen freund die folgede aufgabe geschickt und gemeint das diese aufgabe sehr schön verdeutlich wie gut man mit python programmieren kann. Soweit so gut, jetzt habe ich die Aufgabe gelöst, aber natürlich ist mein kumpel net da, sonder im urlaub und kann mir seine "super" lösung net schicken. Deswegen wollte ich euch mal fragen wie ne vernünftige lösung aussehen würde.

Code: Alles auswählen

# Tree
#              1
#      2              3
#  4      5       6       7
# 8 9   10 11   12 13   14 15

# [value, child1, child2]



t = [1,
          [2,
               [4,
                    [8, None, None],
                    [9, None, None]],
               [5,
                    [10, None, None],
                    [11, None, None]]],
          [3,
               [6,
                    [12, None, None],
                    [13, None, None]],
               [7,
                    [14, None, None],
                    [15, None, None]]]]


# Meine loesung:
myList = []

def pt(level):
    if myList == []:
        myList.append(level[0])
   
    for i in range(1, 3):
        myList.append(level[i][0])
        print level[i][0]
        if level[i][1] != None:
            pt(level[i])


Also eigentlich sortiert ja pt den baum nicht sonder ließt nur die values aus, ich führen aus myList dann nochmal ein .sort aus.

Würde mich über ne antwort freuen!
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Re: Tree sortieren

Beitragvon Rebecca » Montag 21. April 2008, 08:08

cullmann hat geschrieben:mir hat nen freund die folgede aufgabe geschickt

Was genau ist denn die Aufgabe?
Offizielles Python-Tutorial (Deutsche Version)

Urheberrecht, Datenschutz, Informationsfreiheit: Piratenpartei
cullmann
User
Beiträge: 13
Registriert: Donnerstag 10. April 2008, 19:08
Wohnort: Dublin

Beitragvon cullmann » Montag 21. April 2008, 08:10

Verdammt, ich wußte doch das ich was vergessen habe.....

Also die Aufgabe besteht darin den Baum zu sortieren, also die Values der Knoten aufsteigend sortieren aber nicht als Baum dann abspeichern sondern einfach nur in ne liste.
Sorry
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Beitragvon EnTeQuAk » Montag 21. April 2008, 08:47

Der Baum ist zwar irgentwie merkwürdig, aber die Lösung ist relativ einfach.

Ich hätte es so gemacht:

Code: Alles auswählen

In [29]: def flatten(items):
    ret = []
    for item in items:
        if isinstance(item, list):
            ret += flatten(item)
        else:
            ret.append(item)
    return ret
   ....:

In [37]: tree
Out[37]:
[1,
 [2,
  [4, [8, None, None], [9, None, None]],
  [5, [10, None, None], [11, None, None]]],
 [3,
  [6, [12, None, None], [13, None, None]],
  [7, [14, None, None], [15, None, None]]]]

In [38]: sorted(filter(None, flatten(tree)))
Out[38]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]


Wobei man sich das`flatten` aufgrund der bekannten Datenstruktur mit einer List-Comprehension vermutlich sparen kann.

MfG EnTeQuAk
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Montag 21. April 2008, 08:58

Code: Alles auswählen

def flatten(items):
    ret = []
    for item in items:
        try:
            ret.extend(flatten(item))
        except TypeError:
            ret.append(item)
    return ret

Irgendwie eine...komische Aufgabe.

Als Aufruf dann:

Code: Alles auswählen

print sorted(filter(bool, flatten(t)))

Oder als generator:

Code: Alles auswählen

def flatten(items):
    for item in items:
        try:
            for i in flatten(item):
                yield i
        except TypeError:
            yield item
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Beitragvon Rebecca » Montag 21. April 2008, 09:23

filter(None,...) oder filter(bool,...) wuerde auch Elemente mit dem Wert 0 wegschmeissen...
Offizielles Python-Tutorial (Deutsche Version)

Urheberrecht, Datenschutz, Informationsfreiheit: Piratenpartei
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Montag 21. April 2008, 09:30

Gnaah...du hast recht.

Code: Alles auswählen

print sorted(i for i in flatten(t) if isinstance(i, int))
BlackJack

Beitragvon BlackJack » Montag 21. April 2008, 22:09

Also ich finde es ja immer schön, wenn Schüler ihre Lehrer als Freunde ansehen. Dass die die Lösung von Hausaufgaben nicht rausrücken ist aber auch wirklich doof. :twisted:
EyDu
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Montag 21. April 2008, 22:13

Hey, aber cullmann war wenigstens bei seiner Geschichte kreativ :lol:
cullmann
User
Beiträge: 13
Registriert: Donnerstag 10. April 2008, 19:08
Wohnort: Dublin

Beitragvon cullmann » Montag 21. April 2008, 22:23

super alles voller spazzvögel hier
Das war keine verdammte aufgabe von nem Lehr du vogel, hab jetzt auch raus bekommen wo die aufgabe "ursprünglich" herkommt:
http://osdir.com/ml/python.general.german/2003-04/msg00059.html


Aber hey, hauptsache was gesagt.....
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Montag 21. April 2008, 22:28

Pf...paulst auch nich hier rum, nachdem dir geholfen wurde? Ich glaube es hackt :D
querdenker
User
Beiträge: 424
Registriert: Montag 28. Juli 2003, 16:19
Wohnort: /dev/reality

Beitragvon querdenker » Dienstag 22. April 2008, 08:30

Immerhin hat cullmann gleich bei der Eröffnung Code dabei gehabt. :D
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Dienstag 22. April 2008, 10:10

cullmann hat geschrieben:Das war keine verdammte aufgabe von nem Lehr du vogel

Vogel? Das war doch das Signalwort "ich bin ein Troll, schließe meinen Thread" :)
My god, it's full of CARs! | Leonidasvoice vs Modvoice

Wer ist online?

Mitglieder in diesem Forum: Hyperion