algorithm - 如何在 Scheme 中查找列表的分区

Question

假设 Scheme 中有任何给定的列表。这个列表是‘(2 3 4)

我想找到这个列表的所有可能的分区。这意味着一个分区，其中一个列表被分成两个子集，这样列表的每个元素都必须在一个或其他子集中，但不能同时在两个子集中，并且没有元素可以被排除在分割之外。

因此，给定列表 ‘(2 3 4)，我想找到所有可能的分区。这些分区如下:{2, 3} 和 {4}，{2, 4} 和 {3}，最后可能的分区是 {3, 4} 和 {2}。

我希望能够在给定 Scheme 列表的情况下递归地查找所有分区，但我不知道该怎么做。如果有人可以为我提供代码或伪代码，它将对我有帮助! 我相信我将不得不为我的递归函数使用 lambda。

Answer 1

我在 my blog 讨论了几种不同类型的分区，虽然不是这个特定的。例如，考虑一个整数分区是所有正整数集合的集合，这些集合的总和为给定整数。比如4的划分就是集合的集合((1 1 1 1) (1 1 2) (1 3) (2 2) (4))。

构建分区的过程是递归的。有一个单独的分区 0，即空集 ()。有 1 的单个分区，即集合 (1)。有两个 2 的划分，集合 (1 1) 和 (2)。有 3 个分区，集合 (1 1 1)、(1 2) 和 (3)。有五个分区 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