2011-01-13 9 views
6

Sono nuovo al Common Lisp e alla programmazione funzionale, ma ho molta esperienza in linguaggi come C, C++, C#, Java e così via. Ho difficoltà a trovare la lista più annidata all'interno di una lista. Il mio ingresso è qualcosa di simile:Trova l'elenco più annidato all'interno di un elenco in Common Lisp

(0 1 (2 3) 4 (5 (6 (7) 8)) 9) 

Vorrei ottenere l'elenco più annidata all'interno di questa lista che in questo caso è

(7) 

ho avuto un'idea che ho potuto appiattire la lista in qualche modo fino a quando non è rimasta una sola sottoclasse. Per illustrare quello che voglio dire, qui è a pochi passi:

Fase 1. - Ingresso:

(0 1 (2 3) 4 (5 (6 (7) 8)) 9) 

Fase 2. - appiattire su "primo livello":

(0 1 2 3 4 5 (6 (7) 8) 9) 

punto 3. - appiattire su "secondo livello":

(0 1 2 3 4 5 6 (7) 8 9) 

Ora c'è una sola lista annidata a sinistra, il che significa che è stata la lista più nidificato. Ma vedo un problema qui, quando si verificano due o più di tali elenchi. Per favore condividi le tue opinioni su questo.

Ho problemi a mettere questa procedura in realtà in Common Lisp, quindi sarei grato per alcuni suggerimenti nella giusta direzione, forse qualche codice di esempio e così via. Questo è un compito a casa, quindi non mi aspetto una soluzione completa, ma sarei lieto se qualcuno indicasse forse una soluzione più semplice e migliore e la sua implementazione.

+1

Una specie di problema interessante.Penso che quello che farei sarebbe un attraversamento DFS, e registrare la coppia (foglia, profondità della foglia) in una lista, quindi cercare nella pila la foglia con la profondità massima. –

risposta

2

Ecco la mia soluzione (non molto pulita) in CL:

(defun deepest-list (lst) 
    (let ((max-depth 0) ret) 
    (labels ((inner-deepest-lst (lst depth) 
      (cond 
     ((null lst) depth) 
     ((listp (car lst)) 
      (let ((local-max (max 
        (inner-deepest-lst (first lst) (1+ depth)) 
        (inner-deepest-lst (rest lst) (1+ depth))))) 
      (and (> local-max max-depth) (setf ret (first lst) max-depth local-max)) 
      local-max)) 
     (t (inner-deepest-lst (rest lst) depth))))) 
     (inner-deepest-lst lst 1)) 
    ret)) 

edit:

Dopo un secondo pensiero, questa è una soluzione un po 'più pulita:

(defun deepest-list (lst) 
    (labels ((dl (lst depth) 
     (cond 
      ((atom lst) (cons 0 lst)) 
      ((every #'atom lst) (cons depth lst)) 
      (t (funcall (lambda (x y) (if (> (car x) (car y)) x y)) 
       (dl (car lst) (1+ depth)) 
       (dl (cdr lst) depth)))))) 
    (rest (dl lst 0)))) 
+1

Grazie per il tuo commento. Anche se sarei stato grato solo per alcune idee, hai fornito una soluzione funzionante. Sono riuscito a imparare molto da questo prendendo un po 'di tempo e scomposizione. Vedere la tua soluzione e cercare di capirlo mi ha fatto davvero pensare nella giusta direzione. Quindi ti do la risposta accettata per questa domanda. – brozo

+1

Cordiali saluti, ho aggiunto una soluzione più pulita. – yan

2

Il tuo approccio di appiattimento iterativo della lista dovrebbe probabilmente funzionare correttamente, anche se non è il modo più efficiente o (soggettivamente) elegante per farlo.

Se ci sono più di una lista di questo tipo, l'output corretto dipenderà dalla specifica - se dovessi restituirli tutti, o solo il primo, o lanciare un errore?

Se fossi in te, mi piacerebbe dare un'occhiata a una funzione ricorsiva per risolvere il problema. Ogni livello di ricorsione baserebbe fondamentalmente gli elementi di un dato livello delle liste annidate. Pensa a ciò che ogni chiamata ricorsiva dovrebbe fare - è molto semplice se fa clic!

+0

Grazie per il tuo commento. Sì, ho pensato di iniziare a pensare in modo ricorsivo un po '. – brozo

3

Ecco la mia soluzione, utilizzando un approccio simile agli OP. (Nel caso di più elementi più profondi, sono tutti restituiti.)

ho scritto nello Schema, che probabilmente non sarà immediatamente traducibile a Common Lisp, quindi non si sentono che sarebbe una completa regalare. Tuttavia, ha il potenziale per essere spoiler, quindi calpestare con cautela.

(define (deepest lst) 
    (let ((filtered (filter pair? lst))) 
    (cond ((null? filtered) lst) 
      (else (deepest (concatenate filtered)))))) 
+0

Grazie per il tuo commento. La tua risposta mi ha aiutato parecchio, anche se è in Scheme. Tuttavia, ho imparato un po 'di più dalla risposta di yan. Se potessi, ti darei entrambe una risposta accettata, ma poiché è nuovo e la sua risposta mi ha aiutato un po 'di più, ho scelto la sua risposta come accettata. – brozo

+0

Questa è una soluzione molto elegante. –

+1

Il problema con questa soluzione è che "in caso di più elementi deepeest" non restituirà un elenco di questi articoli più profondi ma la concatenazione di questi elenchi. –