List partitions of a number in scheme

Question

I need to represent the partitions of a number in a list. The procedure also takes in arguments that determine the max number of partitions and the max value of the initial partition.

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

Here the initial total is 5, the max number of partitions is 2 and the max initial partition is 4.

Conceptually, I think I should feed the partitioned numbers into a helper function that will construct the partitions for me. But how would I implement that?

Solved it

Answer 1

Here's a possible solution in Racket. First, the partition procedure (based on this algorithm) generates the complete list of partitions for the integer n. Then the list-partitions procedure filters the results as requested:

#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))