finding subsets of length N of a list in scheme

Question

I wrote a function which finds all the subsets of a list already and it works. I'm trying to write a second function where I get all the subsets of N length, but it's not working very well.

This is my code:

(define (subset_length_n n lst)
  (cond 
    [(empty? lst) empty]
    [else (foldr (lambda (x y) (if (equal? (length y) n) (cons y x) x)) empty (powerset lst))]

))

where (powerset lst) gives a list of all the subsets. Am I misunderstanding the purpose of foldr? I was thinking that the program would go through each element of the list of subsets, compare the length to n, cons it onto the empty list if there the same, ignore it if it's not.

But (subset_length_n 2 (list 1 2 3)) gives me (list (list 1 2) 1 2 3) when I want (list (list 1 2) (list 1 3) (list 2 3))

Thanks in advance

Answer 1

When using foldr you don't have to test if the input list is empty, foldr takes care of that for you. And this seems like a job better suited for filter:

(define (subset_length_n n lst)
  (filter (lambda (e) (= (length e) n))
       (powerset lst)))

If you must, you can use foldr for this, but it's a rather contrived solution. You were very close to getting it right! in your code, just change the lambda's parameters, instead of (x y) write (y x). See how a nice indentation and appropriate parameter names go a long way toward writing correct solutions:

(define (subset_length_n n lst)
  (foldr (lambda (e acc)
           (if (= (length e) n)
               (cons e acc)
               acc))
         empty
         (powerset lst)))

Anyway, it works as expected:

(subset_length_n 4 '(1 2 3 4 5))
=> '((1 2 3 4) (1 2 3 5) (1 2 4 5) (1 3 4 5) (2 3 4 5))