CODEWITHSUNDEEP
python
Garvey
Garvey

Reputation: 1309

Divide a list into two, making sum of sublist equal

Assume there is a list L=list(range(N)), and number n1 and n2 where n1+n2=sum(L). I want to def an function to divide L into L1 and L2 so that sum(L1)=n1 and sum(L2)=n2.

How to build this function in an effective way?

Example:

Given: N=7,n1=7,n2=14

We got: L=list(range(7))

We need func(L) returns [3,4] and [0,1,2,5,6]

Upvotes: 0

Views: 97

Answers (2)

576i
576i

Reputation: 8362

@adam-smith's solution was correct, but had two litte errors.

Also, please note you should user lower case letters for variables like lists.

def split_list(l, n1, n2):
    l1, l2 = [], []  # new lists
    x = max(n1, n2)
    for n in reversed(l):
        if n <= x:
            l1.append(n)
            x -= n
        else:
            l2.append(n)
    if n1 < n2:
        l2, l1 = l1, l2

    assert sum(l1) == n1, sum(l1)        
    assert sum(l2) == n2, sum(l2)
    return l1, l2

Upvotes: 0

blhsing
blhsing

Reputation: 106638

This will give you all the possible combinations that satisfy the criteria:

def fit_sum(l, s):
    for i, n in enumerate(l):
        if n == s:
            yield frozenset([n])
        elif n < s:
            for r in fit_sum(l[:i] + l[i+1:], s - n):
                yield frozenset([n, *r])

def func(N, n1, n2):
    L = list(range(N))
    for r in set(fit_sum(L, n1)):
        yield list(r), list(set(L) - r)

for L1, L2 in func(7, 7, 14):
    print('{}, {}'.format(L1, L2))

This outputs:

[0, 3, 4], [1, 2, 5, 6]
[3, 4], [0, 1, 2, 5, 6]
[1, 2, 4], [0, 3, 5, 6]
[0, 2, 5], [1, 3, 4, 6]
[2, 5], [0, 1, 3, 4, 6]
[1, 6], [0, 2, 3, 4, 5]
[0, 1, 6], [2, 3, 4, 5]
[0, 1, 2, 4], [3, 5, 6]

Upvotes: 2

Related Questions