Number Partitioning in R5RS

ساخت وبلاگ

Vote count: 0

I was asked in an internship interview to do a R5RS program that creates a function, let's say two-subsets. This function has to return #t if the list L contains two subsets with equal sums of elements and with equal numbers of elements, otherwise it returns #f. It takes in entry the list L (only positive numbers) and some parameters (that I judge useful. There is no conditions on the number of parameters) all equal to 0 at the beginning.

The requirements as I still remember were as follow: - Do not define other functions and call them inside the "two-subsets" function. - It can only use the following constructs: null?, cond, car, cdr, else, + ,=, not, and, #t, #f, two-subsets (itself for recursive call), the names of the parameters, such as list, sum, ...etc, numeric constants and parentheses.

There were some given examples on the results that we are supposed to have, let's say:

(two-subsets '(7 7) 0 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 '(1 2 3 6 9) 0 0) returns #f. 

I started by writing the signature that it looks to me it should be something like this:

(define two-subsets (lambda (L m n ... other parameters) (cond

The problem is really complicated and it's complexity is obviously more than O(n), I read on it on https://en.wikipedia.org/wiki/Partition_problem .

I tried to start by defining the algorithm first before coding it. I thought about taking as parameters: sum of the list L so in my conditions I'll iterate only on the combinations which sum is <= sum(L)/2. By doing that I can reduce a little bit the complexity of the problem, but still I couldn't figure out how to do it.

It looks like an interesting problem and I really want to know more about it.

asked 23 secs ago

back soft...
ما را در سایت back soft دنبال می کنید

برچسب : نویسنده : استخدام کار backsoft بازدید : 221 تاريخ : چهارشنبه 6 ارديبهشت 1396 ساعت: 22:15