3

segsリスト内のすべての連続するセグメントのリストを返す関数を作成するにはどうすればよいですか？たとえば(segs '(l i s t))、次の答えを生成する必要があります。

(() (t) (s) (s t) (i) (i s) (i s t) (l) (l i) (l i s) (l i s t))

特に、HtDPに記載されている設計原理に従ってこの問題を解決する方法に興味があります（いいえ、これは本の問題ではないので、気軽に話し合ってください！）解決方法は？プログラムの導出に使用する原則はどれですか？

4

2 に答える 2

6

関連する一連の例を作成することから始めます。最も簡単なものから始めます。

(equal? (segs '())
        (list '()))
(equal? (segs '(z))
        (list '()
              '(z)))
(equal? (segs '(y z))
        (list '() '(z)
              '(y) '(y z)))
(equal? (segs '(x y z))
        (list '() '(z) '(y) '(y z)
              '(x) '(x y) '(x y z)))

例を見ると、観察できます (強調するために書式設定を使用しました)。各例の回答には、前の例の回​​答のすべての要素が含まれています。実際、空でないリストの連続したサブシーケンスは、リスト自体の空でないプレフィックスを合わせた末尾の連続したサブシーケンスです。

したがって、メイン関数を保留にして書き込みますnon-empty-prefixes

non-empty-prefixes : list -> (listof non-empty-list)

そのヘルパー関数を使用すると、メイン関数を簡単に記述できます。

(オプション)の呼び出しを繰り返すため、結果として得られる単純な関数の複雑性は低くなりますnon-empty-prefixes。を考慮してください(segs (cons head tail))。これは2(non-empty-prefixes tail)回(segs tail)呼び出し(non-empty-prefixes tail)ます。これは、単純な関数が不必要に悪い複雑さを持っていることを意味します。(non-empty-prefixes (cons head tail))(non-empty-prefixes tail)

問題は、(segs tail)計算(non-empty-prefixes tail)してから忘れてしまうため(segs (cons head tail))、作業をやり直さなければならないことです。解決策は、融合によってその余分な情報を保持し、segs両方non-empty-prefixesの答えを計算する単一の関数にすることです。

segs+ne-prefixes : list -> (values (listof list) (listof non-empty-list))

次にsegs、2 番目の部分をドロップするだけのアダプター関数として定義します。これにより、複雑さに関する主な問題が修正されます。

(編集して追加)についてsegs+ne-prefixes: を定義する 1 つの方法を次に示しますnon-empty-prefixes。(注: 空のリストには空でないプレフィックスはありません。エラーを発生させる必要はありません。)

;; non-empty-prefixes : list -> (listof non-empty-list)
(define (non-empty-prefixes lst)
  (cond [(empty? lst)
         empty]
        [(cons? lst)
         (map (lambda (p) (cons (first lst) p))
              (cons '() (non-empty-prefixes (rest lst))))]))

次segsのようになります。

;; segs : list -> (listof list)
(define (segs lst)
  (cond [(empty? lst) (list '())]
        [(cons? lst)
         (append (segs (rest lst))
                 (non-empty-prefixes lst))]))

次のように融合できます。

;; segs+ne-prefixes : list -> (values (listof list) (listof non-empty-list))
;; Return both the contiguous subsequences and the non-empty prefixes of lst
(define (segs+ne-prefixes lst)
   (cond [(empty? lst)
          ;; Just give the base cases of each function, together
          (values (list '())
                  empty)]
         [(cons? lst)
          (let-values ([(segs-of-rest ne-prefixes-of-rest)
                        ;; Do the recursion on combined function once!
                        (segs+ne-prefixes (rest lst))])
            (let ([ne-prefixes
                   ;; Here's the body of the non-empty-prefixes function
                   ;; (the cons? case)
                   (map (lambda (p) (cons (first lst) p))
                        (cons '() ne-prefixes-of-rest))])
              (values (append segs-of-rest ne-prefixes)
                      ne-prefixes)))]))

この関数は依然として設計レシピに従います (または、私のテストを示した場合はそうなります): 特に、リストの構造的再帰にテンプレートを使用します。valuesHtDP はとについては触れていませんlet-valuesが、情報をグループ化する補助構造を使用して同じことを行うことができます。

HtDP は複雑さについて少し話しますが、この種の計算の再グループ化は通常、「動的プログラミングとメモ化」の下のアルゴリズムコースで詳しく説明されています。2 つの関数を融合する代わりに memoize を使用することに注意してくださいnon-empty-prefixes。それはまた複雑さを修正したでしょう。

append最後にもう 1 つ:終わり近くへの引数は、 へと逆にする必要があります(append ne-prefixes segs-of-rest)。(もちろん、新しい順序を使用するようにすべてのテストを書き直すか、順序に依存しないリスト比較関数を作成/検索することを意味します。) 大きなリスト (約 300 ～ 400 要素) で関数の 2 つのバージョンをベンチマークしてみてください。違いがわかるかどうか、説明できるかどうかを確認してください。(これは設計ではなく、より多くのアルゴリズムの資料です。)

于 2012-01-10T07:57:42.447 に答える
0

2 つの再帰が行われています。最初の再帰は左側から原子を切り取り、2 つ目は右側から原子を切り落とします。これは、2つの関数で再帰的に解決する方法です（私はSchemeに堪能ではないため）。

Start with the FullList variable in function A, 
accumulate right-chop results on FullList from recursive function B, 
then chop off the left character of FullList and call function A with it. 
Stop when an empty list is received.

すべての結果を蓄積すると、あなたはゴールデンです。

于 2012-01-09T23:19:30.650 に答える