CODEWITHSUNDEEP
python
Matthew
Matthew

Reputation: 19

find which number in a list sum up to a certain number but with negative and decimals

I have a quite big listed number that includes negatives, 2nd placed decimal numbers. For example, (10348.94, -984.23, 9429.92). I want to find the sum of a number that adds up from one in one of the list. Also the number in the list can be repeated, and the given sum can be negative.

Here is what I got so far, the repetition and the decimal seems to work but when I try to do a negative numbers both in the list and the given sum it wouldn't work.

def Find(goal, VarienceNum):
    variance = [[Listed] for Listed in VarienceNum]
    newList = []
    result = []

    while variance:
        for holder in variance:
            s = sum(holder)
            for Listed in VarienceNum:
                if Listed >= holder[-1]:
                    if s + Listed < goal:
                        newList.append(holder + [Listed])
                    elif s + Listed == goal:
                        result.append(holder + [Listed])
        variance = newList
        newList = []
    return result
goal=float(input("please enter your goal: "))
VarienceNum=list(map(float,input("please enter the list: ").split()))
print(Find(goal,VarienceNum))

here's the output

Upvotes: 1

Views: 92

Answers (1)

Gershom Maes
Gershom Maes

Reputation: 8170

Get all subsets of the list, check the sum of each subset, and when that sum finally matches the target value return that subset!

def inc_bool_array(arr, ind=0):
    
    '''
    Increments an array of booleans; some examples:
    [ 0, 0, 0 ] -> [ 1, 0, 0 ]
    [ 1, 0, 0 ] -> [ 1, 1, 0 ]
    [ 1, 1, 0 ] -> [ 0, 0, 1 ]
    [ 0, 0, 1 ] -> [ 1, 0, 1 ]
    .
    .
    .
    '''

    if (ind >= len(arr)): return;
    
    if (arr[ind] == 0):
        arr[ind] = 1;
    else:
        arr[ind] = 0;
        inc_bool_array(arr, ind + 1);

def find_subset_sum(target, arr):
    
    size = len(arr);
    pick = [ 0 for n in arr ];
    num_subsets = 2 ** size;
    
    '''
    Loop through every possible subset until we find one such that
    `sum(subset) == target`
    '''
    for n in range(num_subsets):
        
        ''' Subset is determined by the current boolean values in `pick` '''
        subset = [ arr[ind] for ind in range(size) if pick[ind] == 1 ];
        
        if sum(subset) == target: return subset;
        
        ''' Update `pick` to the next set of booleans '''
        inc_bool_array(pick);
    
    return None;

print(find_subset_sum(3, [ 1, 2, 3 ]));
print(find_subset_sum(5, [ 1, 2, 3 ]));
print(find_subset_sum(6, [ 1, 2, 3 ]));
print(find_subset_sum(7, [ 1, 2, 3 ]));

print(find_subset_sum(3, [ -1, 5, 8 ]));
print(find_subset_sum(4, [ -1, 5, 8 ]));
print(find_subset_sum(5, [ -1, 5, 8 ]));
print(find_subset_sum(6, [ -1, 5, 8 ]));
print(find_subset_sum(7, [ -1, 5, 8 ]));
print(find_subset_sum(8, [ -1, 5, 8 ]));
print(find_subset_sum(12, [ -1, 5, 8 ]));
print(find_subset_sum(13, [ -1, 5, 8 ]));

The hard part here is getting all possible subsets of the list. Getting all subsets is a matter of choosing "include" or "exclude" for every item in the list (2 options per element results in 2^n possible choices, and 2^n possible subsets).

In order to enumerate all these choices I use a simple array called pick which is composed of boolean values; one boolean value for each value in the source array. Each boolean represents an include/exclude choice for its corresponding value in the source array. The array starts full of only 0, representing the choice of "exclude" for each item. Then a function called inc_bool_array is used to update pick to the next set of values. This means pick will take on these values over time:

Step 1: [ 0, 0, 0, 0, 0, ... ]
Step 2: [ 1, 0, 0, 0, 0, ... ]
Step 3: [ 0, 1, 0, 0, 0, ... ]
Step 4: [ 1, 1, 0, 0, 0, ... ]
Step 5: [ 0, 0, 1, 0, 0, ... ]
Step 6: [ 1, 0, 1, 0, 0, ... ]
Step 7: [ 0, 1, 1, 0, 0, ... ]
Step 8: [ 1, 1, 1, 0, 0, ... ]
Step 9: [ 0, 0, 0, 1, 0, ... ]
.
.
.

Gradually every possible combination of 0s and 1s will occur. Then pick is used to generate a subset which only contains values corresponding to a 1, simply using a generator with an if condition:

subset = [ arr[ind] for ind in range(len(arr)) if pick[ind] == 1 ]

Upvotes: 2

Related Questions