解析式不能表达的子集和函数

          姜咏江  Email：accsys@126.com

   解析式不能表达的函数一般只能够用真值表的形式来表示，只是函数的定义域和值域都必须是有限个值。著名的子集和subset_sum问题就是这样一个函数。如何将这个函数表达出来？第一，先要确定函数的定义域；第二，求出函数的值域并建立对应关系。

一、添右组合法

   N个数组成的数集的子集应该有2N个。如何能够快速地求出这2N个子集？我这里提供一种方法，叫添右组合法。我相信这是一种最快的求全部子集与子集和方法。

表 1是添右组合方法求全部非零子集的例子。

表 1  添右组合例子

这种方法操作的具体步骤如下：

（1）将每个数做为一元子集；

（2）将右面的数依次排到左面数的后面，形成二元子集，直到最后一个元素排到所有左面一元集合中，至此形成全部二元子集；

（3）如果子集的最后已是最右面的数，不再添加，以下各次添加亦如此；

（4）将二元子集依次添加上右面的元素，形成三元子集；

（5）将三元子集依次添加上右面的元素，形成四元子集；

（6）将四元子集添加上右面的元素，最后得到全集结束。

   这种方法我们称为添右组合。按照添右组合这种方法，对于n元的集合也可以依次得到一元到n元的全部子集。

二、添右组合定理

   添右组合法得到的子集有两个问题必须回答。

1. 这种方法得到的是全部子集吗？

2. 这些子集中有没有重复的子集？

添右组合定理：n元集合用添右组合法得到全部非空子集为2n-1个。

   这个定理需要证明全部非空子集一个不少，且都不相同。

这里用归纳法来证明：

显然一个元素的集合没有多大意义，因而下面证明从2个元素的集合开始。

（1）设n=2，那么A=｛a1,a2｝，则A的转移组合得到的子集为｛a1｝｛a2｝｛a1,a2｝子集数为22-1=3说明子集数正好且不重复。

（2）设n=k时得到的子集｛a1｝｛a2｝...｛a1,a2,...,ak｝满足条件子集数为2k-1，且不重复。那么当n=k+1时，则除添加子集｛ak+1｝之外，需要将n=k时得到2k-1个子集全部添加ak+1，形成的全部子集为

｛a1｝｛a2｝...｛ak｝｛ak+1｝...｛a1,a2,...,ak｝｛a1,a2,...,ak,ak+1｝

子集总数应为2k-1+2k=2×2k-1=2k+1-1,说明子集总数正确。

（3）假设n=k+1时出现了重复子集，不妨设有子集Bi=Bj，i≠j，它们之中都包含ak+1。那么将ak+1从它们之中取出，则应有Bi｛ak+1｝=Bj｛ak+1｝，这与n=k时得到的子集不重复子集矛盾。故没有重复子集产生。

证毕。

   理论上添右组合法可以快速求出任意有限数集的全部子集与其和，也就是构造出子集和函数的真值表表达方式。

三、设计的软件及使用

   我用FoxPro用添右组合法设计了Subset_sum软件。用这款软件可以求出任意有限数集的全部子集，顺带求出其元素和。由于计算机提供的资源不同，软件在不同的计算机上运行的数据范围会受到具体计算机的制约。

例1. 验证数集S={1,2,7,14,49,98,343,686,2409,2793,16808,17206,117705,117993}子集有没有和为138457的子集。

    此题摘自《算法导论》，书中只给了一个答案。我们来看看有几个。

如图 1所示，运行subset.exe，选择BuildSetCreateSet，然后输入S集合的数，这样就可以生成其全部非零子集。

图 1  Subset_sum建立集合

   得到非零子集之后，就建立了Subset_sum函数，其定义域与值域可以选择TruthTablec查看。总共有10383个子集，也就是214-1个。

   如果想猜测验证所给数为子集和的个数，可以选择GuessCheck项，然后输入猜测的数，回车。图 2 是输入138457后得到的4个子集，而书中只给出了一个。可见软件是比较全面地寻找了满足条件的子集。这一过程实际上是在值域中搜索，依据真值表列了出全部满足条件的子集，速度之快已是O(n)级多项式时间复杂度。

   讨论pnp的问题，不应将函数的建立时间包括在其中。P类问题借用函数y=x1+x2+...+xn得出了子集和，而这个解析式是早已建立好的通用函数，其定义域包含了Subset_sumh函数的定义域，故而可以借用。用这个表达式计算必须保证自变量属于Subset_sumh函数的定义域才可以。不要以为使用函数y=x1+x2+...+xn不是查表，实际上设计计算机运算器就是制作了一张真值表。在使用该公式求子集和时，难道不用看看子集的元素有哪些吗？

   由和值去查找所有的和为此数的集合，即是所谓的np问题。这里从214-1个数中查找子集和是138457完全是一个O(n)级多项式时间复杂度查找问题。变量是n，而不是14。在子集和问题中，请记住2k-1的k是一个常量！

图 2  输入138457得到4个子集

   软件使用中，如果只想验证某个数是不是这个集合的子集和，那么请选择YesNot项菜单，输入猜测的数，系统会立即给出“是”与“否”的回答。

此外，该软件还可以依据和值及元素数来查找满足条件的全部子集，这要选择菜单Conditions来获得。这样可以减少那些不必要的子集出现。

四、结论

   做为退休的人，已经没有了利益的过多纷争，能做的事情是凭借兴趣，锻炼一下自己的脑子，免于过早痴呆。

   结论是有的，那就是P类问题和NP类问题是同一类问题。P=NP。

2014-12-9

附软件：

BuidSubset_Sum.rar