Write a function two-subsets in Scheme that takes a list L of positive integers (duplicates are possible, zero is not considered a positive integer) and some auxiliary parameters of your choice

06 Aug Write a function two-subsets in Scheme that takes a list L of positive integers (duplicates are possible, zero is not considered a positive integer) and some auxiliary parameters of your choice

The function two-subsets returns #t if the list L contains two subsets with equal sums of elements and with equal numbers of elements. Otherwise (if two subsets satisfying the condition above do not exist), the function returns #f. Assume that the list L contains at least two integers.

Note that here, it is not required that the whole list be split into two subsets. In HW3, some elements of the list could be left out from the two subsets. Therefore, every list, which is a solution to HW2 is also be a solution to HW3. However, there are solutions to HW3 that are not solutions to HW2.

It is up to you to choose the auxiliary parameters that two-subsets takes. All auxiliary parameters must be numeric (not lists) and should have initial values set to zero. For example, if L is ‘(1 2 3) and if you decide to use two additional auxiliary parameters, then two-subsets must be called as follows:

(two-subsets ‘(1 2 3) 0 0)

If there are three auxiliary parameters, then the function must be called:

(two-subsets ‘(1 2 3) 0 0 0) and so on.
Note that the function must be called two-subsets. Other names will not be accepted. The list must precede the auxiliary parameters, which are initially set to zeroes.

There is no need to optimize your code. Try to come up with a working solution.

Examples (for the sake of illustration, two auxiliary parameters are used):

(two-subsets ‘(7 7) 0 0) returns #t. The two subsets are {7} and {7}.

(two-subsets ‘(7 7 1) 0 0) returns #t. The two subsets are {7} and {7}.

(two-subsets ‘(5 3 2 4) 0 0) returns #t. The two subsets are {2, 5} and {3, 4}.
(two-subsets ‘(5 3 21 2 4) 0 0) returns #t. The two subsets are {2, 5} and {3, 4}.

(two-subsets ‘(2 13 7 5 16 11) 0 0) returns #t. The two subsets are {7, 11} and {5, 13}.

(two-subsets ‘(1 2 3 6 9) 0 0) returns #f.

(two-subsets ‘(10 4 7 102 36 6 17 54) 0 0) returns #f.

The whole solution must be packed in one recursive function two-subsets which must look as follows:

 

(define two-subsets (lambda (<list L followed by numeric parameters of your choice initially set to zero>)     (cond   … )))

 

In other words, you have to choose your auxiliary parameters and define a COND statement.

Nested COND statements are allowed.

Inside COND, you can use ONLY the following constructs:

– null?

– cond

– car

– cdr

– else

– +

– =

– not

– and

– #t

– #f

– two-subsets

– the names of your parameters, such as list, sum, etc.

–  numeric constants, such as 0, 1, 2, etc.

–  parentheses

You cannot use a construct if it is not listed above. In other words, your code must define and use only one function, two-subsets, which must be defined using the template and the constructs listed above. The use of built-in functions is not allowed.

If your program uses a construct not on the list, then it is not a solution to the homework.

It is not allowed to bypass the homework requirements by packing several functions in one function definition using a numeric flag. In other words, for one value of the numeric flag the function does one thing and for other value of the flag the function does something else.

Here is an example of packing several function using a numeric flag as a second parameter:

 

(define two-subsets (lambda (list flag)

(cond

((= flag 0) the function implements one type of functionality)

((= flag 1) the function implements a second type of functionality)

(else the function implements a third type of functionality )
)))

 

Here, we have three functions (corresponding to flag values of 0, 1, and 2) packed in one COND statement. The flag is not related to the problem at hand and it used for the sole purpose of packing different functionalities in one COND statement. This is not allowed.

 

 

Before you start working on HW3, read carefully the first HW2 solution which I have posted, the recursive method that takes four parameters: the list, the two subset sums and the two subset counts:

public boolean recursiveCheck(Node list, int sum1, int sum2, int count1, int count2) {
if(list==null) return (sum1 == sum2 && count1 == count2);
return recursiveCheck(list.next, sum1 + list.number, sum2, count1 + 1, count2)
|| recursiveCheck(list.next,sum1, sum2 + list.number, count1, count2 + 1);
}

In HW3, you have to translate this method  into Scheme using the OR function. Both recursive calls are made on the rest of the list (list.next in Java corresponds to (cdr list) in Scheme). In the first recursive call, we add the current element (list.number in Java corresponds to (car list) in Scheme) to sum1 and we increment count1, whereas in the second recursive call, we add the current element to sum2 and we increment count2. The logic is the following: the recursive function must return #t if at least one of the recursive calls returns #t.

Once you translate the solution to HW2 into Scheme, you will be only one short step away from the solution to HW3: you need to consider one more recursive case, the one in which the current element is not added to either subset. Remember that in HW3, the union of the two subsets might be less than the whole list, i.e., some numbers might not belong to either subset.