假设Scheme中有任何给定的列表。这份清单是‘(2 3 4)
我想找到此列表的所有可能分区。这意味着一个分区，其中列表被分成两个子集，使得列表的每个元素必须在一个或另一个子集中，但不能同时在两个子集中，并且不能将任何元素排除在分割之外。
所以，给定列表‘(2 3 4)，我想找到所有这些可能的分区。这些分区如下：{2,3}和{4}，{2,4}和{3}，最终可能的分区为{3,4}和{2}。
我希望能够以递归方式查找给出Scheme中列表的所有分区，但我对如何执行此操作没有任何想法。如果有人能为我提供代码或伪代码将帮助我！我相信我将不得不使用lambda作为我的递归函数。
我在my blog讨论了几种不同类型的分区，尽管不是这个特定分区。例如，假设整数分区是与给定整数相加的所有正整数集的集合。例如，4的分区是组的集合（（111 1）（1 1 2）（1 3）（2 2）（4））。
构建分区的过程是递归的。有一个0的分区，空集（）。单个分区为1，即集合（1）。有两个分区2，集合（1 1）和（2）。有三个分区3，集合（1 1 1），（1 2）和（3）。有4个分区，4个集合（1 1 1 1），（1 1 2），（1 3），（2 2）和（4）。存在5个分区，即集合（1 1 1 1 1），（1 1 1 2），（1 2 2），（1 1 3），（1 4），（2 3）和（5）。等等。在每种情况下，通过将小于或等于期望整数n的每个整数x添加到由n-x的分区形成的所有集合来确定下一个更大的分区集合，从而消除任何重复。以下是我实现的方法：
Petite Chez Scheme Version 8.4
Copyright (c) 1985-2011 Cadence Research Systems
> (define (set-cons x xs)
(if (member x xs) xs
(cons x xs)))
> (define (parts n)
(if (zero? n) (list (list))
(let x-loop ((x 1) (xs (list)))
(if (= x n) (cons (list n) xs)
(let y-loop ((yss (parts (- n x))) (xs xs))
(if (null? yss) (x-loop (+ x 1) xs)
(y-loop (cdr yss)
(set-cons (sort < (cons x (car yss)))
xs))))))))
> (parts 6)
((6) (3 3) (2 2 2) (2 4) (1 1 4) (1 1 2 2) (1 1 1 1 2)
(1 1 1 1 1 1) (1 1 1 3) (1 2 3) (1 5))
我不打算为你解决你的作业，但你的解决方案将类似于上面给出的解决方案。您需要以递归方式陈述算法，然后编写代码来实现该算法。您的递归将是这样的：对于集合中的每个项目，将项目添加到集合的其余项目的每个分区，从而消除重复。
那会让你开始。如果您有具体问题，请返回此处获取更多帮助。
编辑：这是我的解决方案。我会告诉你它是如何工作的。
(define range (case-lambda ; start, start+step, ..., start+step<stop
((stop) (range 0 stop (if (negative? stop) -1 1)))
((start stop) (range start stop (if (< start stop) 1 -1)))
((start stop step) (let ((le? (if (negative? step) >= <=)))
(let loop ((x start) (xs (list)))
(if (le? stop x) (reverse xs) (loop (+ x step) (cons x xs))))))
(else (error 'range "unrecognized arguments"))))
(define (sum xs) (apply + xs)) ; sum of elements of xs
(define digits (case-lambda ; list of base-b digits of n
((n) (digits n 10))
((n b) (do ((n n (quotient n b))
(ds (list) (cons (modulo n b) ds)))
((zero? n) ds)))))
(define (part k xs) ; k'th lexicographical left-partition of xs
(let loop ((ds (reverse (digits k 2))) (xs xs) (ys (list)))
(if (null? ds) (reverse ys)
(if (zero? (car ds))
(loop (cdr ds) (cdr xs) ys)
(loop (cdr ds) (cdr xs) (cons (car xs) ys))))))
(define (max-lcm xs) ; max lcm of part-sums of 2-partitions of xs
(let ((len (length xs)) (tot (sum xs)))
(apply max (map (lambda (s) (lcm s (- tot s)))
(map sum (map (lambda (k) (part k xs))
(range (expt 2 (- len 1)))))))))
(display (max-lcm '(2 3 4))) (newline) ; 20
(display (max-lcm '(2 3 4 6))) (newline) ; 56
您可以使用内置的combinations过程找到列表的所有2个分区。这个想法是，对于(len-k)-combination的每个元素，k-combination中将有一个元素补充它，产生一对列表，其联合是原始列表，交集是空列表。
例如：
(define (2-partitions lst)
(define (combine left right)
(map (lambda (x y) (list x y)) left right))
(let loop ((m (sub1 (length lst)))
(n 1))
(cond
((< m n) '())
((= m n)
(let* ((l (combinations lst m))
(half (/ (length l) 2)))
(combine (take l half)
(reverse (drop l half)))))
(else
(append
(combine (combinations lst m)
(reverse (combinations lst n)))
(loop (sub1 m) (add1 n)))))))
那么您可以将分区构建为：
(2-partitions '(2 3 4))
=> '(((2 3) (4))
((2 4) (3))
((3 4) (2)))
(2-partitions '(4 6 7 9))
=> '(((4 6 7) (9))
((4 6 9) (7))
((4 7 9) (6))
((6 7 9) (4))
((4 6) (7 9))
((4 7) (6 9))
((6 7) (4 9)))
此外，您可以找到分区的最大lcm：
(define (max-lcm lst)
(define (local-lcm arg)
(lcm (apply + (car arg))
(apply + (cadr arg))))
(apply max (map local-lcm (2-partitions lst))))
例如：
(max-lcm '(2 3 4))
=> 20
(max-lcm '(4 6 7 9))
=> 165
对列表进行分区是简单的递归非确定性编程。
给定一个元素，我们把它放在一个袋子里，或另一个袋子里。
第一个元素将进入第一个包，不失一般性。
最后一个元素必须只进入一个空袋子，如果那个时候存在的话。由于我们首先将第一个元素放入第一个包中，因此它只能是第二个：
(define (two-parts xs)
(if (or (null? xs) (null? (cdr xs)))
(list xs '())
(let go ((acc (list (list (car xs)) '())) ; the two bags
(xs (cdr xs)) ; the rest of list
(i (- (length xs) 1)) ; and its length
(z '()))
(if (= i 1) ; the last element in the list is reached:
(if (null? (cadr acc)) ; the 2nd bag is empty:
(cons (list (car acc) (list (car xs))) ; add only to the empty 2nd
z) ; otherwise,
(cons (list (cons (car xs) (car acc)) (cadr acc)) ; two solutions,
(cons (list (car acc) (cons (car xs) (cadr acc))) ; adding to
z))) ; either of the two bags;
(go (list (cons (car xs) (car acc)) (cadr acc)) ; all solutions after
(cdr xs) ; adding to the 1st bag
(- i 1) ; and then,
(go (list (car acc) (cons (car xs) (cadr acc))) ; all solutions
(cdr xs) ; after adding
(- i 1) ; to the 2nd instead
z))))))
就是这样！
在写这篇文章时，我得到了this earlier related answer of mine的帮助。
测试：
(two-parts (list 1 2 3))
; => '(((2 1) (3)) ((3 1) (2)) ((1) (3 2)))
(two-parts (list 1 2 3 4))
; => '(((3 2 1) (4))
; ((4 2 1) (3))
; ((2 1) (4 3))
; ((4 3 1) (2))
; ((3 1) (4 2))
; ((4 1) (3 2))
; ((1) (4 3 2)))
可以在返回之前反转零件，或者当然;我想保持代码简洁干净，没有多余的细节。
编辑：该代码利用Richard Bird的技术，用(append (g A) (g B))替换(g' A (g' B z))，其中(append (g A) y) = (g' A y)和z的初始值是一个空列表。
另一种可能性是将go的嵌套调用放在lambda后面（确实是OP确实）并在外部调用go完成其工作时激活，使整个函数尾递归，主要在CPS style。