给定集合的不同和计数器

Question

我正在编写这个代码（基本代码归功于Shreyansi Arun），它打印给定集合的所有子集的总和：

def subsetSums(arr, l, r, sum=0):
    # Print current subset
    if l > r:
        global k
        print(sum,end=" ")
        k += 1
        return

    # Subset including arr[l]
    subsetSums(arr, l + 1, r, sum + arr[l])

    # Subset excluding arr[l]
    subsetSums(arr, l + 1, r, sum)

k = 0
arr = [0.5, 0.5, 1.5, 1.5, 2, 3, 5, 5]
n = len(arr)

subsetSums(arr, 0, n - 1)

print ("\n Combinations:",k)

我正在尝试对其进行调整，以获得一个计数。在我离开代码时，变量k用作求和计数器。但是，我希望此计数器仅在结果和不等于之前的任何值时增加

例如，在此代码中，结果如下所示：

19.0 14.0 14.0 9.0 16.0 11.0 11.0 6.0 17.0 12.0 12.0 [...]
Combinations: 256

例如，可以看到，第二个和第三个结果是14.0。在这些情况下，我希望避免增加k，因为第三个和等于第二个和。否则，我的所有组合将得到256（对于长度为8的数组）。相同的条件应适用于数组中任何即将出现的重复数，而不仅仅是直接的后续数

Answer 1

这里更好的方法是维护一个哈希表来检查已经出现的总和

def subsetSums(arr, l, r,sum=0):
# Print current subset
if l > r:
    global k
    global sumHash
    print(sum, end=" ")
    if(sum not in sumHash):
        k += 1
    sumHash[sum] = True
    return

# Subset including arr[l]
subsetSums(arr, l + 1, r,sum + arr[l])

# Subset excluding arr[l]
subsetSums(arr, l + 1, r, sum)


k = 0
sumHash = dict()
arr = [0.5, 0.5, 1.5, 1.5, 2, 3, 5, 5]
n = len(arr)

subsetSums(arr, 0, n - 1)

print("\n Combinations:", k)

Answer 2

创建一个集合来保存所有总和。将每个总和添加到集合中，集合的长度将是不同总和的数量

def subsetSums(arr, l, r, sum=0, allSums = None):
    if allSums is None:
        allSums = set()
    # Print current subset
    if l > r:
        allSums.add(sum)
        print(sum,end=" ")
        return len(allSums)

    # Subset including arr[l]
    subsetSums(arr, l + 1, r, sum + arr[l], allSums)

    # Subset excluding arr[l]
    return subsetSums(arr, l + 1, r, sum, allSums)

arr = [0.5, 0.5, 1.5, 1.5, 2, 3, 5, 5]
n = len(arr)

k = subsetSums(arr, 0, n - 1)

Answer 3

我不想继续遍历所有的2ⁿ子集，而是像这样构建一组和：

sums = {0}
for x in arr:
    sums |= {s + x for s in sums}
print(len(sums))

或与functools.reduce一起：

>>> len(reduce(lambda sums, x: sums | {s + x for s in sums}, arr, {0}))
39