list - 列出方案中数字的分区

Question

我需要在列表中表示一个数字的分区。该过程还接受用于确定最大分区数和初始分区最大值的参数。

(list-partitions 5 2 4)
>((4 1) (3 2))

这里初始总数为 5，最大分区数为 2，最大初始分区数为 4。

从概念上讲，我认为我应该将分区数字输入一个辅助函数，该函数将为我构建分区。但是我将如何实现呢？

解决了

Answer 1

这是 Racket 中一个可能的解决方案。首先，该partition过程（基于此算法）为整数生成完整的分区列表n。然后list-partitions程序按要求过滤结果：

#lang racket

(define (partition n)
  (let loop ((n n)
             (acc '()))
    (if (zero? n)
        (list acc)
        (append-map (lambda (i)
                      (loop (- n i) (cons i acc)))
                    (reverse (build-list n add1))))))

(define (list-partitions n max-number max-init)
  (take (filter (lambda (lst)
                  (<= (apply max lst) max-init))
                (partition n))
        max-number))

(list-partitions 5 2 4)
> '((1 4) (2 3))