Vfrdtyky

I am asked to define a recursive function that takes in a list and then assigns the values of that list among two other lists in such a way that when you take the sum of each of those two lists you get two results that are in close proximity to each other.

Example:

If I run:

print(proximity_lists([5, 8, 8, 9, 17, 21, 24, 27, 31, 41]))

I get back two lists :

[31, 27, 21, 9, 8]          #sum = 96



[41, 24, 17, 8, 5]          #sum = 95

This is how I did it, however I can't get my head around understanding how to return two lists in a recursive function. So far I was comfortable with conditions where I had to return one list.

This is my code so far:

def proximity_lists(lst, lst1 = , lst2 = ):

    """

    parameters : lst of type list;

    returns : returns two lists such that the sum of the elements in the lst1

              is in the proximity of the sum of the elements in the lst2

    """

    if not lst:

        if abs(sum(lst1)-sum(lst2)) in range(5):         

            return lst1, lst2

    else:

        return {Not sure what to put here} + proximity_lists(lst[1:])

As far as range() goes, it can take anything for an argument as long as it's the closest they can get in the proximity of each other. I picked 5 because based on the example output above the difference between them is 1.

I need to add that this has to be done without the help of any modules.It has be done using simple functions.

This is potentially not the optimal solution in terms of performance (exponential complexity), but maybe it gets you started:

def proximity_lists(values):

    def _recursion(values, list1, list2):

        if len(values) == 0:

            return list1, list2

        head, tail = values[0], values[1:]

        r1, r2 = _recursion(tail, list1 + [head], list2)

        s1, s2 = _recursion(tail, list1, list2 + [head])

        if abs(sum(r1) - sum(r2)) < abs(sum(s1) - sum(s2)):

            return r1, r2

        return s1, s2



    return _recursion(values, , )



values = [5, 8, 8, 9, 17, 21, 24, 27, 31, 41]

s1, s2 = proximity_lists(values)

print(sum(s1), sum(s2))

print(s1)

print(s2)



96 95

[24, 31, 41]

[5, 8, 8, 9, 17, 21, 27]

If it is not OK to have a wrapper function, just call _recursion(values, , ) directly.

You can find all permutations of the original input for the first list, and filter the original to obtain the second. This answer assumes that "close proximity" means a difference less than or equal to 1 between the sums of the two lists:

from collections import Counter



def close_proximity(d, _dist = 1):

  def _valid(c, _original):

    return abs(sum(c) - sum([i for i in _original if i not in c])) <= _dist

  def combos(_d, current = ):

    if _valid(current, _d) and current:

      yield current

    else:

      for i in _d:

        _c1, _c2 = Counter(current+[i]), Counter(_d)

        if all(_c2[a] >= b for a, b in _c1.items()):

          yield from combos(_d, current+[i])

  return combos(d)



start = [5, 8, 8, 9, 17, 21, 24, 27, 31, 41]

t = next(close_proximity(start))

_c = [i for i in start if i not in t]

print(t, _c, abs(sum(t) - sum(_c)))

Output:

[5, 8, 8, 9, 17, 21, 27] [24, 31, 41] 1

I can't get my head around understanding how to return two lists in a
recursive function.

Here's a simple solution that produces your original result but without extra arguments, inner functions, etc. It just keeps augmenting the lesser list from the next available value:

def proximity_lists(array):

    if array:

        head, *tail = array



        a, b = proximity_lists(tail)



        ([a, b][sum(b) < sum(a)]).append(head)



        return [a, b]



    return [, ]

USAGE

>>> proximity_lists([5, 8, 8, 9, 17, 21, 24, 27, 31, 41])

[[41, 24, 17, 8, 5], [31, 27, 21, 9, 8]]

>>>