RUBY tree_depth eines Arrays

marekb

marekb

Doppel-As
Hallo, ich habe da eine Aufgabe:
Ich soll die Baumtiefe eines beliebig mehrdimensionalen Arrays bestimmen.
Die Funktion soll so aussehen:
array.tree_depth
Ich soll das rekursiv machen leider bin ich da mit meinem Latein etwas am Ende.
Meine Lösung war mit Iteration:

Code:
def ary?(obj)
 obj.is_a?(Array)
end

class Array
 def tree_depth
   ary?(self)? tree_depth_(self,1,1): raise(RuntimeError)
 end
 
 def tree_depth_(array,curdepth,max)
       cd = curdepth
       md = max
       cd > md ? md = cd : md
       max = md
   array.each { |a| ary?(a) ? md = tree_depth_(a, cd+1,md) : md }
     return md
 end
end

ary_t1=[[1,[2,[3,5]]]]
p ary_t1.tree_depth

Über eine andere Lösung würde ich mich sehr freuen.
 
Hehe, das musste ich vor vielen Jahren mal in ner Klausur in Prolog schreiben. Was hab ich Prolog gehasst. ;)
Aber ich muss gestehen dass Prolog zu lernen mir ne Menge gebracht hat, weil man wirklich gezwungen ist Rekursion zu verstehen und zu verinnerlichen. ;)

Ich denke in pseudo code sollte das etwa so aussehen:
Code:
def calcDepth(list):
   head = list[0] # first element
   tail = list[1:] # list of all elements, except the first

   if tail is None and head is not type(list):
      return 0

   depthHead = 1 + calcDepth(head)
   depthTail = 1 + calcDepth(tail)

   if depthHead > depthTail:
      return depthHead
   else:
      return depthTail
Das ist fast syntaktisch korrekter Python code. Allerdings ist es so noch nicht ganz korrekt, du musst natuerlich noch entsprechende null checks und so einbauen, sonst verschluckt er sich.
Kann auch sein dass es selbst dann nicht ganz korrekt ist, hab's jetzt einfach ungetestet runtergeschrieben.
Aber ich denke das sollte dich in die richtige Richtung schubsen.

Edit:

Na gut, weil ich's so lang nicht mehr gemacht hab, hab ich's grad zum Spass mal in Python ausgearbeitet:
Code:
def calcDepth(aList):
    if aList is None or type(aList) is not list:
        return 0
    if len(aList) <= 0:
        return 1

    head = aList[0] # first element
    if len(aList) > 1:
        tail = aList[1:] # list of all elements, except the first
    else:
        tail = None

    if tail is None and type(head) is not list:
        return 1

    depthHead = 1 + calcDepth(head)
    if tail is not None:
        depthTail = calcDepth(tail)
    else:
        depthTail = 0

    if depthHead > depthTail:
        return depthHead
    else:
        return depthTail

foo=[[[2, 3, [5, 3]]], [2, 3, 4, 5], [[[[[[[[5, [2], [[[]]]]]]]]], 5, 4]]]
print calcDepth(foo)
mfg,
bytepool
 
Zuletzt bearbeitet:
Hey danke ^^ Ja über rekursion sollte die Aufgabe eigentlich gemacht werden.
Mir ist Python nun nicht so geläufig, sind das alles verschachtelte if-Anweisungen?
 
Mir ist Python nun nicht so geläufig, sind das alles verschachtelte if-Anweisungen?
Hehe, ich nehme an du beziehst dich darauf dass du nirgendwo ein "end" siehst? ;)
Python ist white-space gesteuert, das Ende eines Blocks wird ueber die Einrueckung erreicht. D.h. da sind eigentlich keine verschachtelten ifs. Ich seh jedenfalls keine.

Edit:
Gar nicht so einfach, obiges Programm war IMHO immer nocht nicht korrekt, so sollte es jetzt eigentlich stimmen, das ist auch gleich eleganter und einfacher zu verstehen: ;)
Code:
def calcDepth(aList):
    if len(aList) <= 0: # is empty list
        return 1

    head = aList[0] # first element
    if len(aList) > 1:
        tail = aList[1:] # list of all elements, except the first
    else:
        tail = None

    if type(head) is list:
        depthHead = calcDepth(head) + 1
    else:
        depthHead = 1

    if tail is not None:
        depthTail = calcDepth(tail)
    else:
        depthTail = 0

    if depthHead > depthTail:
        return depthHead
    else:
        return depthTail

foo=[[[2, 3, [5, 3]]], [2, 3, 4, 5], [[[[[[[[5, [2], [[[]]]]]]]]], 5, 4]]]
print calcDepth(foo)

Edit2:
Eventuell kurz zur Erklaerung: Dieses splitten in Kopf (head) und Restliste (tail) ist ein gaengiges Muster bei der Rekursion und laesst sich eigentlich fuer Listen immer in dieser Form implementieren.

Dabei ist zu beachten dass tail immer eine neue Liste ist, d.h. im ersten Aufruf wuerden die Variablen fuer die Liste [1, 2, 3] so aussehen: head = 1, tail = [2, 3].
Deswegen wird bei calcDepth(tail) auch nichts addiert, weil jedes Erzeugen einer Restliste automatisch eine Ebene hinzufuegt.

mfg,
bytepool
 
Zuletzt bearbeitet:
Hmm, und weil ich ein Nerd bin und in letzter Zeit ein wenig Programmierentzug hab, hab ich es auch nochmal in Lisp geschrieben. ;p

Code:
(defun calcDepth (alist)
  (if alist
    (let ((head (first alist)) (tail (rest alist)) (depthHead nil) (depthTail nil))
        (if (listp head)
          (setq depthHead (+ 1 (calcDepth head)))
          (setq depthHead 1) )
        (if tail
          (setq depthTail (calcDepth tail))
          (setq depthTail 0) )
        (if (> depthHead depthTail) depthHead depthTail))
    1))

(setq mylist '(((2 3 (5 3))) (2 3 4 5) ((((((((5 (2) ((())))))))))) 5 4))
(print (calcDepth mylist))
Edit: Prolog muesste so richtig sein:
Code:
depth([], 1) :- !.
depth(A, 1) :- atom(A), !.
depth(N, 1) :- number(N), !.

depth([H|[]], Result) :-
        depth(H, DepthHead),
        !,
        Result is DepthHead + 1.

depth([H|T], Result) :-
        depth(H, DepthHead),
        depth(T, DepthTail),
        DepthHead > DepthTail,
        !,
        Result is DepthHead + 1.

depth([H|T], Result) :-
        depth(H, DepthHead),
        depth(T, DepthTail),
        DepthHead < DepthTail,
        !,
        Result = DepthTail.

?- depth([[[2, 3, [5, 3]]], [2, 3, 4, 5], [[[[[[[[5, [2], [[[]]]]]]]]], 5, 4]]], X).
mfg,
bytepool
 
Zuletzt bearbeitet:

Ähnliche Themen

RUBY: Mehrdimensionale Arrays und Objekte

Ubuntu X / dbus problem

Composite oder Svideo Ausgang mit Geforce

tilp lässt sich nicht installieren

Ausgabe in *.txt Datei & Struct

Zurück
Oben