生成一组 Subset-Distinct-Sum 整数的算法

Question

我正在尝试为纸牌游戏创建一个计分系统，该系统通过设置每张纸牌的点值来排除计分上的平局，这样任何两种纸牌组合都不能加起来得到相同的分数。 (对于这种特殊情况，我需要一组 17 个整数，因为有 17 张可计分卡。)

我已经尝试了几种启发式方法(各种风选程序，采用整数数组，迭代生成随机子集，并丢弃那些出现在共享公共(public)总和的子集中的子集)；然后详尽地验证结果(通过枚举它们的子集)。

据我所知，此类集合大小的理论限制接近 log2(n)，其中 n 是从中得出子集不同和子集的超集成员数。然而，虽然我已经能够接近这个，但我无法匹配它。到目前为止，我最好的结果是一组 13 个整数，从 10,000 到 25,000,000 之间的 250,000 个整数中提取，以百计(后者对算法无关紧要，但它是我的用例的域约束):

[332600,708900,2130500,2435900,5322500,7564200,10594500,12776200,17326700,17925700,22004400,23334700,24764900]

我四处寻找，发现大多数 SDS 生成器都是序列生成器，它们不会假装创建密集集，而是能够无限期地继续生成越来越大的数字(例如 Conway-Guy 序列)。我没有这样的限制，并且更喜欢一个更密集的集合而不需要彼此之间的序列关系。

(我确实考虑过使用 Conway-Guy 序列 n=2..18 * 10,000，但结果集的范围比我想要的更广。我也非常喜欢更通用的算法。)

编辑:为清楚起见，我正在寻找一种方法(非确定性或动态编程方法很好)来生成比通过简单枚举指数或使用像 Conway-Guy 这样的序列所提供的更密集的 SDS 集。我希望，通过放弃“序列生成器”约束，我可以找到比此类序列提供的更接近的数字。

Answer 1

对于任何 N 值，很容易生成 Floor(Log2(N))-1数字(我们称之为集合“S”)使得:

1. S的所有成员都小于或等于N，并且

2. S 的两个不同子集的总和不相同，并且

3. S 的所有成员彼此相差在两倍之内。

您的怀疑是正确的，因为 S 在任何意义上都不可扩展(您无法向其添加更多成员)

方法:

1. 对于 N，找到 T = 2^P ，其中 T 是小于或等于 N 的两个中的最高幂。即:

   • P = Floor( Log2(N) ) , 和
   • T = 2^P

2. 那么S的成员可以生成为:

   • for( i=0 to P-2 ): S(i) = 2^i + 2^(P-1)
   • 或者，换句话说，S(i) = 2^i, for 0<= i < P-1

这样总共有 P-1(或 Floor(Log2(N))-1)个成员。 S 的两个不同子集总和可以等于同一个数吗？否:

证明

让我们考虑 S 的任意两个子集:U 和 V，它们是不同的(也就是说，它们没有共同的成员)。则U之和为:

Sum(U) = O(U)*(T/2) + Sum(2^i| S(i):U)

在哪里

• O(U)是集合U的阶(它有多少个元素)，
• “S(i):U”表示“S(i) 是 U 的一个元素”，并且
• “|”是条件运算符(意​​思是“给定...”或“其中...”)，

因此，将最后两个放在一起，Sum(2^i| S(i):U)只是表示“作为 U 元素的两个的所有幂的总和”(记住 S(i) = 2^i))。

同样，V 的总和是:

Sum(V) = O(V)*(2^(P-1)) + Sum(2^i| S(i):V)

现在因为 U 和 V 不同:Sum(2^i| S(i):U)永远不会相等，因为两个不同的幂的和永远不会相等。

另外，因为 Sum(2^i; 0 <= i < P-1) = 2^(P-1)-1) , 这些两个的幂之和必须总是小于 2^P-1 .这意味着 U 和 V 的总和只能在以下情况下相等:

O(U)*(2^(P-1)) = O(V)*(2^(P-1))

或

O(U) = O(V)

也就是说，如果 U 和 V 具有相同数量的元素，则第一项将相等(因为第二项永远不会像第一项中的任何差异一样大)。

在这种情况下 ( O(U) = (O(V) ) 第一项相等，因此 Sum(U) 将等于 Sum(V) 如果它们的第二项(二进制和)也相等。然而，我们已经知道它们永远不可能相等，因此，Sum(U) = Sum(V) 永远不可能为真。 .