1

n と sum をパラメーターとして使用し、合計を合計できるすべての数値 (1 から n まで) を表示するスキーム プログラムを作成するにはどうすればよいですか? このような：

（10 10を見つける）</p>

((10) (9 , 1) (8 , 2) (7 , 3) (7 ,2 , 1) (6 ,4) (6 , 3, 1) (5 , 4 , 1) (5 , 3 , 2) (4 ,3 ,2 ,1))

私は1つを見つけました：

(define (find n sum) 
  (cond ((<=  sum 0) (list '())) 
        ((<= n 0) '()) 
        (else (append 
                 (find (- n 1) sum) 
                 (map (lambda (x) (cons n x)) 
                  (find (- n 1) (- sum n)))))))

しかし、それは非効率的であり、私はより良いものを望んでいます. ありがとうございました。

4

3 に答える 3

0

ケースを処理しないことを除いて、ソリューションは一般的に(= n s)正しいです。ここに解決策があります：

(define (find n s)
  (cond ((or (<= s 0) (<= n 0)) '())
        (else (append (if (= n s)
                          (list (list n))
                          (map (lambda (rest) (cons n rest))
                               (find (- n 1) (- s n))))
                      (find (- n 1) s)))))

> (find 10 10)
((10) (9 1) (8 2) (7 3) (7 2 1) (6 4) (6 3 1) (5 4 1) (5 3 2) (4 3 2 1))

これが特に効率的であるとは言いません。末尾再帰ではなく、結果をメモ化もしません。パフォーマンス結果は次のとおりです。

> (time (length (find 100 100)))
running stats for (length (find 100 100)):
    10 collections
    766 ms elapsed cpu time, including 263 ms collecting
    770 ms elapsed real time, including 263 ms collecting
    345788912 bytes allocated
444793
>
于 2013-05-18T01:51:38.810 に答える
0

これは、整数分割問題または部分集合和問題に似ていますが、厳密には同じではありません。これは整数パーティションの問題ではありません。整数パーティションでは数値の繰り返しが許可されているためです (ここでは、範囲内の各数値の 1 回の出現のみを許可しています)。

これは部分集合和問題 (動的計画法によって多かれ少なかれ効率的に解くことができる) に似ていますが、解法は、与えられた数に追加される可能性のある数の部分集合をすべて生成するように適応させる必要があります。その問題の元の定式化のように、サブセットは 1 つだけです。Scheme を使用して動的プログラミング ソリューションを実装することは可能ですが、可変テーブルの実装にマトリックス ライブラリなどを使用しない限り、少し面倒です。

別の可能な解決策を次に示します。今回は、範囲の累乗セット[1, n]を生成し、各サブセットを順番にチェックして、合計が期待値に追加されるかどうかを確認します。ただし、これは依然として力ずくのアプローチです。

; helper procedure for generating a list of numbers in the range [start, end]
(define (range start end)
  (let loop ((acc '())
             (i end))
    (if (< i start)
        acc
        (loop (cons i acc) (sub1 i)))))

; helper procedure for generating the power set of a given list
(define (powerset set)
  (if (null? set)
      '(())
      (let ((rest (powerset (cdr set))))
        (append (map (lambda (element) (cons (car set) element))
                     rest)
                rest))))

; the solution is simple using the above procedures    
(define (find n sum)
  (filter (lambda (s) (= sum (apply + s)))
          (powerset (range 1 n))))

; test it, it works!
(find 10 10)
=> '((1 2 3 4) (1 2 7) (1 3 6) (1 4 5) (1 9) (2 3 5) (2 8) (3 7) (4 6) (10))

アップデート

前のソリューションは正しい結果を生成しますが、一部のサブセットのみに関心がある場合でも、パワー セットのリスト全体を生成するため、メモリの使用効率が低下します。Racket Scheme では、次のように遅延シーケンスを使用すると、必要に応じて値のみを生成することができます (ただし、注意してください - 最初のソリューションの方が高速です!)。

; it's the same power set algorithm, but using lazy streams
(define (powerset set)
  (if (stream-empty? set)
      (stream '())
      (let ((rest (powerset (stream-rest set))))
        (stream-append
         (stream-map (lambda (e) (cons (stream-first set) e))
                     rest)
         rest))))

; same algorithm as before, but using lazy streams
(define (find n sum)
  (stream-filter (lambda (s) (= sum (apply + s)))
                 (powerset (in-range 1 (add1 n)))))

; convert the resulting stream into a list, for displaying purposes
(stream->list (find 10 10))
=> '((1 2 3 4) (1 2 7) (1 3 6) (1 4 5) (1 9) (2 3 5) (2 8) (3 7) (4 6) (10))
于 2013-05-17T15:35:03.580 に答える