Creating a partition of a set in Scheme

问题:

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.

回答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.

回答2:

For a first pass, you may wish to avoid trying to couple "subset" logic to "do two subsets add to the same value" logic. Small procedures are easier to write than long ones.

But this can be kind of a complicated problem.

One way to approach it is called "wishful thinking." We'll work from the end: what is the last step in solving this problem? Comparing whether two subsets of the same length sum to the same value. So, let's solve that. Then we just do that to all the subsets of the same length. But now we need to know: what are all the groups of subsets of the same length? If we solved that, then everything to the end is finished. So let's solve that. Then we'll just apply that to the set of all subsets. But now we need to know: how do we get the set of all subsets? If we solved that, then everything to the end is finished. We'll just apply it to our set. But now we need to know: what is our set? —oh! that's the problem itself. So we're done!

Actually it's a little trickier in the fine details, but with the above exposition I think you can see the logic of this chain:

(find-first-equal-sum ; we can stop as soon as #t, if there is #t
  (make-pairs ; problem only wants us to consider pairs
    (sum-subsets ;we need sums eventually
       (at-least-two-in-a-group ; can't make pairs without at least two in a group
        (group-by-length ; only care about matching subsets of the same length
         (at-least-length-2 ; singles can't match because each element of a set is unique
          (subsets problem-set)))))))

Note: I did actually write this program and test it before posting. The above "outline" is copied directly from DrRacket.