103. 特殊的子集和:最优解(Special subset sums: optimum)

\(S(A)\)是大小为\(n\)的集合\(A\)中所有元素的和,若任取集合\(A\)中的任意两个非空且没有交集的子集\(B\)\(C\)都满足下面两个条件,我们就称\(A\)是的特殊的和集:

  • \(S(B)\ne S(C)\),也就是说任意子集所有元素的和均不相同;
  • 如果集合\(B\)中的元素比集合\(C\)多,则\(S(B)>S(C)\)

对于给定的\(n\),我们称使得\(S(A)\)最小的集合\(A\)为最优特殊和集,前五个最优特殊和集如下:

  • \(n=1:\{1\}\)
  • \(n=2:\{1,2\}\)
  • \(n=3:\{2,3,4\}\)
  • \(n=4:\{3,5,6,7\}\)
  • \(n=5:\{6,9,11,12,13\}\)

从上面的规律可以猜测,似乎对于一个给定的最优特殊和集\(A=\{a_1,a_2,\cdots,a_n\}\),下一个最优特殊和集将是\(B=\{b,a_1+b,a_2+b,\cdots,a_n+b\}\),其中\(b\)是集合\(A\)中“正中间”的元素。

应用这条规则,我们猜测\(n=6\)时的最优特殊和集为\(A=\{11,17,20,22,23,24\}\),相应的所有元素和\(S(A)=117\)。然而事实并非如此,我们的方法只能找到近似最优特殊和集,实际上对于\(n=6\),最优特殊和集\(A=\{11,18,19,20,22,25\}\),相应的\(S(A)=115\),对应的集合数字的字符串是\(111819202225\)

若集合\(A\)\(n=7\)的最优特殊和集,求其对应的集合数字串。

分析:这道题与第105题高度相关,所以我们可以放在一起来解决,两道题的核心问题都在于找到一个合适算法来判断某个给定的集合是否是特殊和集。特殊和集的判断标准有两个,第一个是任意两个包含元素个数相同的非空不相交子集,其元素和不相等;第二个是任意两个包含元素个数不同的非空不相交子集,包含元素多的子集的元素和要大于包含元素较小的子集的元素和。尤其需要注意的,这里说的任意两个非空且没有交集的子集,并不意味着这两个子集是互补的,即两个子集的并集可能并不等于集合\(A\)本身。假设我们用\(L\)表示集合中的元素个数,则上述规则可以形式化表述如下:

$$ \begin{cases} S( B) \neq S( C) & L( B) =L( C)\\ ( S( B) -S( C)( L( B) -L( C)) >0 & L( B) \neq L( C) \end{cases} $$

现在的问题是对于任意一个集合,如何高效的判断它是否是一个特殊和集?一个可行的方法是这样的:我们先将集合中的元素进行升序排列,然后使用\(itertools\)库中的\(combinations\)函数依次生成不同元素个数的子集,首先是元素个数为一的子集,实际上就是各个元素本身,只要集合中没有重复元素,长度为一的子集显然符合两个特殊和集的标准,我们可以把它存入到一个列表\(arr\)中。然后是长度为二的子集,我们首先判断它与列表中的子集是否都满足特殊和集的两个标准,如果不满足则这个集合就不是特殊和集,可以直接返回\(False\),否则就把这个子集存入到列表\(arr\)中。如果遍历了所有子集后,都没有找到不符合两个标准的子集,则这个集合就是一个特殊和集。

下面的问题是如何生成一个最优特殊和集,题目中给出的生成最优特殊和集的规则是错误的,但有一部分可供参考:一是通过元素数为\(n\)的最优特殊和集生成元素数为\(n+1\)最优特殊和集时,\(n+1\)最优特殊和集的第一个元素是\(n\)特殊和集的居中的元素(假定集合元素升序排列,当元素个数为偶数时,居中元素指第\(\lfloor n/2\rfloor\)个元素);二是我们可以通过将\(n\)最大特殊子集的元素两两相加来生成\((n+1)\)特殊子集的元素。我们可以使用\(combinatios\)函数来生成这些集合,因为\(combinations\)函数生成的组合是依据字典排序的,所以这些集合的和也是升序排列的,所以找到的第一个符合要求的特殊和集就是最优特殊和集。

令人意外的是,我们最终找到的长度为七的最优特殊和集,实际上完全可以根据题目中给出的规则来生成,虽然这个规则本身是错误的,这个巧合无疑让花了很长时间去写代码的同学感受到了莫大的伤害:

# time cost = 421 ms ± 88.1 ms

from itertools import combinations

def is_valid(B,tup):
    L,S = tup
    if len(B) == L:
        return sum(B) != S
    else:
        return (sum(B)-S)*(len(B)-L)>0

def is_special_sumsets(s):
    arr = [(1,x) for x in sorted(s)]
    for r in range(2,len(s)):
        for i in combinations(sorted(s),r):
            for j in arr:
                if not is_valid(i,j):
                    return False
            arr.append((len(i),sum(i)))
    return True

def main(arr=[11,18,19,20,22,25],n=7):
    optimum = set(arr[len(arr)//2:] + sorted([x+y for x in arr for y in arr]))
    for i in combinations(optimum,n):
        if is_special_sumsets(i):
            return "".join([str(x) for x in i])