6

Common Lisp と関数型プログラミングは初めてですが、C、C++、C#、Java などの言語の経験は豊富です。リスト内で最もネストされたリストを見つけるのに苦労しています。私の入力は次のようなものです：

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

このリスト内で最もネストされたリストを取得したいのですが、この場合は

(7)

サブリストが 1 つだけになるまで、どうにかしてリストを平坦化できるという考えがありました。私が言いたいことを説明するために、ここにいくつかのステップがあります：

ステップ 1. - 入力:

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

ステップ 2. - 「第 1 レベル」で平坦化:

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

ステップ 3. - 「第 2 レベル」で平坦化:

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

これで、ネストされたリストが 1 つだけ残っています。これは、それが最もネストされたリストであることを意味します。しかし、このようなリストが 2 つ以上発生する場合、ここで問題が発生します。これについてあなたの考えを共有してください。

Common Lisp でこの手順を実現するのに問題があるので、正しい方向へのポインタ、サンプル コードなどを教えていただければ幸いです。これは宿題なので、完全な解決策は期待していませんが、誰かがおそらくより簡単でより良い解決策とその実装を指摘してくれるとうれしいです.

4

3 に答える 3

3

OPと同様のアプローチを使用した私のソリューションは次のとおりです。(最深部が複数ある場合は全て返却されます。)

私はこれをSchemeで書きましたが、それはおそらくすぐにCommon Lispに翻訳できるものではないので、完全なプレゼントになるとは思いません。ただし、ネタバレの可能性もありますので、十分注意してください。

(define (deepest lst)
  (let ((filtered (filter pair? lst)))
    (cond ((null? filtered) lst)
          (else (deepest (concatenate filtered))))))
于 2011-01-13T20:24:27.913 に答える
2

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))

編集：

もう一度考えた後、これは少しクリーンなソリューションです。

(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))))
于 2011-01-13T20:28:48.270 に答える
2

リストを繰り返しフラット化するアプローチは、おそらくうまくいくはずですが、それは最も効率的または（主観的に）エレガントな方法ではありません。

そのようなリストが複数ある場合、正しい出力は仕様によって異なります。それらすべてを返すか、最初のリストだけを返すか、またはエラーをスローする必要がありますか?

もし私があなたなら、問題を解決するための再帰関数を考え出すでしょう。再帰の各レベルは、基本的に、ネストされたリストの特定のレベルの要素を処理します。それぞれの再帰呼び出しが何をすべきかを考えてみてください - 一度クリックすればとても簡単です!

于 2011-01-13T16:48:10.507 に答える