我正在尝试为纸牌游戏创建一个计分系统,该系统通过设置每张纸牌的点值来排除计分上的平局,这样任何两种纸牌组合都不能加起来得到相同的分数。 (对于这种特殊情况,我需要一组 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 集。我希望,通过放弃“序列生成器”约束,我可以找到比此类序列提供的更接近的数字。
最佳答案
对于任何 N 值,很容易生成 Floor(Log2(N))-1
数字(我们称之为集合“S”)使得:
S的所有成员都小于或等于N,并且
S 的两个不同子集的总和不相同,并且
S 的所有成员彼此相差在两倍之内。
您的怀疑是正确的,因为 S 在任何意义上都不可扩展(您无法向其添加更多成员)
方法:
对于 N,找到
T = 2^P
,其中 T 是小于或等于 N 的两个中的最高幂。即:-
P = Floor( Log2(N) )
, 和 -
T = 2^P
-
那么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)
永远不可能为真。 .
关于生成一组 Subset-Distinct-Sum 整数的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25977701/