Рекурсивная функция, которая берет один список и возвращает два списка

Question

Меня просят определить рекурсивную функцию, которая принимает список и затем назначает значения этого списка среди двух других списков таким образом , что при получении суммы из каждого из этих двух списков вы получаете два результата, которые находятся в непосредственной близости друг от друга.

Пример

Если я бегу:

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

Я получаю два списка:

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

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

Вот как я это сделал, однако я не могу понять, как вернуть два списка в рекурсивной функции. До сих пор мне было комфортно в условиях, когда мне приходилось возвращать один список.

Это мой код:

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

Что касается range(), то для аргумента может потребоваться что угодно, лишь бы он был ближайшим, который они могут получить в непосредственной близости друг от друга . Я выбрал 5, потому что в приведенном выше примере разница между ними равна 1.

Мне нужно добавить, что это должно быть сделано без помощи каких-либо модулей. Это было сделано с помощью простых функций.

Answer 1

Вы можете найти все перестановки исходного ввода для первого списка и отфильтровать оригинал, чтобы получить второй. В этом ответе предполагается, что «близкая близость» означает разницу, меньшую или равную 1 между суммами двух списков:

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

Выход:

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

Answer 2

Я не могу понять, как вернуть два списка в рекурсивной функции.

Вот простое решение, которое дает исходный результат, но без дополнительных аргументов, внутренние функциии т. д. Он просто продолжает увеличивать меньший список из следующего доступного значения:

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

Answer 3

Это потенциально не оптимальное решение с точки зрения производительности (экспоненциальная сложность), но, возможно, оно поможет вам начать:

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]

Если не все нормально иметь функцию-обертку, просто вызовите _recursion(values, [], []) напрямую.