CODEWITHSUNDEEP
pythonlistrecursion
user10158754
user10158754

Reputation:

Recursive function that takes in one list and returns two lists

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.

Upvotes: 2

Views: 1232

Answers (3)

cdlane
cdlane

Reputation: 41872

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]]
>>>

Upvotes: 0

Ajax1234
Ajax1234

Reputation: 71451

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

Upvotes: 0

Matthias Ossadnik
Matthias Ossadnik

Reputation: 911

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.

Upvotes: 1

Related Questions