Scheme, two subsets with equal sums and equals amounts of elements
Source code must be in R5RS.
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 the difference from HW2: 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 ()
(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.
