RUBY tree_depth eines Arrays

Dieses Thema im Forum "Ruby, php, Perl, Python ..." wurde erstellt von marekb, 24.01.2011.

  1. marekb

    marekb Doppel-As

    Dabei seit:
    15.07.2006
    Beiträge:
    121
    Zustimmungen:
    0
    Ort:
    Hamburg
    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.
     
  2. Anzeige

    Schau dir mal diese Kategorie an. Dort findest du bestimmt etwas.
    Registrieren bzw. einloggen, um diese und auch andere Anzeigen zu deaktivieren
  3. #2 bytepool, 24.01.2011
    Zuletzt bearbeitet: 24.01.2011
    bytepool

    bytepool Code Monkey

    Dabei seit:
    12.07.2003
    Beiträge:
    791
    Zustimmungen:
    0
    Ort:
    /home/sweden/göteborg
    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
     
  4. marekb

    marekb Doppel-As

    Dabei seit:
    15.07.2006
    Beiträge:
    121
    Zustimmungen:
    0
    Ort:
    Hamburg
    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?
     
  5. #4 bytepool, 24.01.2011
    Zuletzt bearbeitet: 24.01.2011
    bytepool

    bytepool Code Monkey

    Dabei seit:
    12.07.2003
    Beiträge:
    791
    Zustimmungen:
    0
    Ort:
    /home/sweden/göteborg
    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
     
  6. #5 bytepool, 25.01.2011
    Zuletzt bearbeitet: 27.01.2011
    bytepool

    bytepool Code Monkey

    Dabei seit:
    12.07.2003
    Beiträge:
    791
    Zustimmungen:
    0
    Ort:
    /home/sweden/göteborg
    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
     
Thema:

RUBY tree_depth eines Arrays

Die Seite wird geladen...

RUBY tree_depth eines Arrays - Ähnliche Themen

  1. Ruby in Version 2.3 erschienen

    Ruby in Version 2.3 erschienen: Die freie Skriptsprache Ruby ist in einer neuen Version verfügbar. Version 2.3.0 bringt nach Angaben der Entwickler viele Neuerungen, darunter ein...
  2. Ruby 2.2.0 einsatzbereit

    Ruby 2.2.0 einsatzbereit: Die Ruby-Entwickler haben ihre freie Skriptsprache in der Version 2.2 freigegeben. Seit der letzten Version kamen mehrere interessante Neuerungen...
  3. Ruby on Rails 4.2 freigegeben

    Ruby on Rails 4.2 freigegeben: Die Rails-Entwickler haben die Version 4.2 des auf Ruby beruhenden Web-Frameworks veröffentlicht. Die neue Version kommt mit nicht allzu vielen...
  4. Ruby on Rails 4.1 freigegeben

    Ruby on Rails 4.1 freigegeben: Die Rails-Entwickler haben die Version 4.1 des auf Ruby beruhenden Web-Frameworks veröffentlicht. Die neue Version kommt mit vielen Neuerungen und...
  5. Ruby on Rails 4.0 freigegeben

    Ruby on Rails 4.0 freigegeben: Die Rails-Entwickler haben die Version 4.0 des auf Ruby beruhenden Web-Frameworks veröffentlicht. Die neue Version kommt mit vielen Neuerungen und...