Subset-AVG - Finding a subset of List Which Matches Known Rational Number

Refresh

4 weeks ago

Views

10 time

0

I've asked this on math overflow and used comments to clarify/overstate my question. I hope it has the intended effect and doesn't come off as jarring.

I'm attempting to find what subset of numbers reach a known average.

I have a list of known values, negative and possible decimals. They look something like this {-.32,-.64,-.12,.08,-.54,-.43, ...}

It's around 50 numbers in some cases, though this problem would be tested for other cases as well.

The set mostly contains negative decimal numbers, while in rare cases, has a few positive decimals - it never has whole numbers.

I also have a known value, which I know to be the average of some subset of the above list.

The known value is similar to -.03.

I'm uncertain of the grouping mechanism used, but seemed to reach stack overflow trying to solve this problem when not grouping.

I've attempted a few ways of going about solving this problem. I'm using Python 3.6 and imported numpy as np.

I'm wondering if the "subset-avg" code I've adapted from another solution for subset-sum here (I'll give due credit when i can find that question again) is not the most efficient way/if there's any huge mistake in my even attempting to resolve this that I haven't seen.

Thanks in advance for any thoughts.

def subset_avg(numbers, target, partial=[],depth=1):
    # create AVG function

    # set average of partial
    a = np.mean(partial)

    # check if the partial sum is equals to target


    if a != target:
        print("Currently Testing the Following Subset's " " " + "Average(%s)  =  %s\n\n" % (partial, round(a,2)))
    print(depth)

    if a == target or round(a,2) == target:

            print('\n\n')
            print("************")
            print("************")
            print('\n\n')
            print("Found Subset AVG " + "Average(%s)  =  %s" % (partial, target))
            print('\n\n')
            print("************")
            print("************")
            print('\n\n')
    print(depth)        
    # for each number in range of list
    for i in range(len(numbers)):
        # set n = current iteration in list
        n = numbers[i]
        # remaining values is current iteration + 1 through end of list
        remaining = numbers[i+1:]
        # calculate mean of partial, set partial = partial plus n 
        subset_avg(remaining, target, partial + [n],depth+1)

# Example of use
x = [-.32,-.64,-.12,.08,-.54,-.43]

subset_avg(x,-.03)

0 answers