子集-AVG-查找与已知有理数匹配的列表的子集 [英] Subset-AVG - Finding a subset of List Which Matches Known Rational Number

问题描述

我已经在数学溢出上问过这个问题，并使用注释来澄清/夸大我的问题。我希望它能达到预期的效果，不要给人留下不和谐的印象。

我正在尝试找出哪个数字子集达到已知的平均值。

我有一个已知值、负数和可能的小数的列表。它们看起来类似于{-.32，-.64，-.12，.08，-.54，-.43，...}

在某些情况下约为50个数字，但此问题也会在其他情况下进行测试。

该集合大多数包含负十进制数，但极少数情况下有少数正小数-它从不包含整数。

我还有一个已知值，我知道它是上述列表的某个子集的平均值。

已知值类似于-.03。

我不确定使用的分组机制，但在未分组时尝试解决此问题时似乎遇到了堆栈溢出。

我已经尝试了几种方法来解决这个问题。 我正在使用Python3.6和导入的NumPy作为NP。

我想知道我改编自另一个子集求和解决方案的"subset-avg"代码(当我再次发现这个问题时，我会给予应有的评价)是否不是最有效的方式/如果我试图解决这个问题，是否存在任何我没有看到的巨大错误。

提前感谢您的任何想法。

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

" % (partial, round(a,2)))
    print(depth)

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

            print('

')
            print("************")
            print("************")
            print('

')
            print("Found Subset AVG " + "Average(%s)  =  %s" % (partial, target))
            print('

')
            print("************")
            print("************")
            print('

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

推荐答案

以下是我针对另一个问题(here)发布的子集求和算法的解决方案。由于该算法遍历潜在的解大小，因此很容易对其进行调整以搜索平均值。

iSubSum()函数接受3个参数：目标平均值、值列表和一个可选的舍入精度参数。它是一个生成器，所以当在循环中使用时，它将产生所有可能的解。您也可以使用next()函数快速获得第一个解。这应该会比暴力方法更快地产生结果，特别是对于大型列表。

该函数基于子集和算法的修改版本，该算法以索引列表的形式返回解决方案。这是为了区分具有来自原始列表中不同索引的重复值的组合。

from bisect import bisect_right
from itertools import accumulate
def iSubAverage(M,A,P=0):
    smallSize     = 20
    smallSums     = set()
    def subSumForSize(S,A,size,failedSums=None):
        nextSum = A[size-2][2] if size>1 else 0
        index   = bisect_right([a for a,_,_ in A],S-nextSum) # max element for target
        A       = A[:index]
        if len(A) < size:    return                  # not enough elements for size
        if A[size-1][2]  > S: return                 # minimum sum > target
        maxSum = A[-1][2]
        if len(A) > size: maxSum -= A[-size-1][2]
        if maxSum < S:  return                       # maximum sum < target
        if len(A) <= smallSize and S not in smallSums: return

        if failedSums is None: failedSums = set()

        while index >= size: 
            index -= 1
            a,i,ca = A[index]
            if size == 1:
                if a == S: yield [i]
                continue
            c0 = A[index-size][2] if index>size else 0
            if ca-c0 < S: break
            subS = S-a
            if subS in failedSums: continue # known unreachable sum
            failed = True
            for result in subSumForSize(subS,A[:index],size-1,failedSums):
                yield result+[i]
                failed = False
            if failed: failedSums.add(subS)

    if not A: return
    if M < 0: M,A = -M,[-a for a in A] # must have positive target
    offset = max(0,-min(A)) # circumvent negatives (requires loop on sizes)
    A      = sorted([(round(a+offset,P),i) for i,a in enumerate(A)])
    cumA   = accumulate(a for a,i in A)
    A      = [(a,i,ca) for (a,i),ca in zip(A,cumA)]

    for a,_,_ in A[:smallSize]:
        newSums = [a+s for s in smallSums] + [a]
        smallSums.update(newSums)

    for size in range(1,len(A)+1):
        subS  = round(M*size,P)
        if subS != round(M*size,P*2): continue # fractional numerator
        subS += round(offset*size,P)
        for result in subSumForSize(subS,A,size):
            yield result

若要获取实际值，iSubAvg()函数将索引映射到列表中的相应值：

def iSubAvg(M,A,P=0):
    for iA in iSubAverage(M,A,P):
        yield sorted([A[i] for i in iA])

L       = [-.32,-.64,-.12,.08,-.54,-.43]
targetL = -0.02
for solution in iSubAvg(targetL,L,2):
    print(solution)

# [-0.12, 0.08]   (there isn't a solution for -0.03)

K = [0.72, 0.69, 0.81, -0.28, 0.6, 0.59, 0.77, 0.46, 0.36, 0.66, 0.88, 0.88, 0.9, -0.24, 0.5, -0.5, 0.46, 0.96, -0.22, -0.8, -0.13, 0.87, 0.78, 0.2]    
targetK = -0.02
for solution in iSubAvg(targetK,K,2):
    print(solution)

# [-0.5, 0.46]
# [-0.5, 0.46]
# [-0.8, -0.22, 0.96]
# [-0.5, -0.28, 0.72]
# [-0.28, -0.24, 0.46]
# [-0.28, -0.24, 0.46]
# [-0.5, -0.24, 0.2, 0.46]
# [-0.5, -0.24, 0.2, 0.46]
# [-0.8, -0.28, -0.24, -0.22, 0.46, 0.96]
# [-0.8, -0.28, -0.24, -0.22, 0.46, 0.96]


next(iSubAvg(0.165,K,2))

# [-0.8, -0.28, -0.24, 0.66, 0.69, 0.96]

注意，该函数返回所有组合，包括对源列表中重复值的重复。如果您不需要这些副本，可以将它们过滤掉

这篇关于子集-AVG-查找与已知有理数匹配的列表的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！