Creating a partition of a set in Scheme

Question

I'm pretty new to scheme overall and I'm having some issues with figuring out an assignment for school. So please no full answers, just looking for a little insight or a nudge in the right direction so I can figure this out on my own.

The problem is as follows: Given a list of numbers, determine whether two subsets can be made from those numbers of equivalent sum and # of items. So for example, if the given set is (1 1) then my program should return #t, otherwise #f.

Here is what I have written so far (even though it gives no output at the moment)

(define l (list '(7 5)))

(define s1 0)
(define s2 0)
(define l1 0)
(define l2 0)

(define two-subsets
  (lambda (l s1 s2 l1 l2)
    (if (null? l)
          (if (and (= s1 s2) (= l1 l2))
              (#t))
          (if (not (and (= s1 s2) (= l1 l2)))
              (#f)))
    (or ((two-subsets(cdr l) (+ s1 1) s2 (+ l1 1) l2) (two-subsets(cdr l) s1 (+s2 1) l1 (+ l2 1))))))

My function should recursively add items to either subset 1 (s1, l1) or subset 2 (s2, l2) until it reaches the base case where it determines whether or not the subsets are of equivalent size and sum. I feel like my logic is there / close, but I'm unsure how to implement these ideas properly in scheme.

EDIT I should add that, as a part of the assignment, I must use recursion. I wish DrRacket gave more debugging info because when I hit run it gives no errors, but also no output.

Answer 1

Issues

There are some issues in your code.

First

This creates a list of a list:

(list '(7 5))  ; => ((7 5))

A cdr of that is always an empty list.

(cdr (list '(7 5)))  ; => ()

A single list is created in this way:

(define l (list 7 5))

or this way:

(define l '(7 5))

Second

You use parenthesis in Scheme for application. This:

(#t)

means "execute the function #t". But #t is not a function, it is a Boolean value. And Boolean values can not be executed.

Your can return a Boolean value directly

#t

or you can return a function returning the value

(lambda () #t)

but you can not execute true.

Third

Same problem in or. The following code:

(or ((two-subsets (cdr l) (+ s1 1) s2 (+ l1 1) l2)
     (two-subsets (cdr l) s1 (+s2 1) l1 (+ l2 1))))

means: two-subsets must return a function. The function returned by the first two-subsets call gets executed with the function returned by the second two-subsets call. And the single result value gets passed to or. This is probably not what you want.

If you want to or the two return values of the two calls to two-subsets, you have to remove two parenthesis.

(or (two-subsets (cdr l) (+ s1 1) s2 (+ l1 1) l2)
    (two-subsets (cdr l) s1 (+s2 1) l1 (+ l2 1)))

Hints

• Define a function which matches your end condition. The function takes two list arguments and checks, if they have the same size (length) and sum (you can use apply to pass a list to +). Spoiler
• Write a function which iterates through all possible subsets. And call your match function with each combination. Iteration is done by recursion in Scheme. Either define a function, which calls itself or use a named let.