由网友(扒掉你の内内)分享简介：我正在对组合数学算法的一些练习，并试图找出如何解决以下问题：I'm making some exercises on combinatorics algorithm and trying to figure out how to solve the question below:由于一组25位，设置（可选择）15（...

我正在对组合数学算法的一些练习，并试图找出如何解决以下问题：

I'm making some exercises on combinatorics algorithm and trying to figure out how to solve the question below:

由于一组25位，设置（可选择）15（非置换和秩序NON事项）：

Given a group of 25 bits, set (choose) 15 (non-permutable and order NON matters):

n!/(k!(n-k)!) = 3.268.760

现在，每一种可能性构造一个矩阵，其中我过每一个独特的25bit成员对所有其他25bit成员，其中 在它的关系，必须有至少11共同设置好的位（唯一，不零）。

Now for every of these possibilities construct a matrix where I cross every unique 25bit member against all other 25bit member where in the relation in between it there must be at least 11 common setted bits (only ones, not zeroes).

让我试着再说明presenting它作为二进制数据，所以第一个成员是：

Let me try to illustrate representing it as binary data, so the first member would be:

0000000000111111111111111 (10 zeros and 15 ones) or (15 bits set on 25 bits)
0000000001011111111111111 second member
0000000001101111111111111 third member
0000000001110111111111111 and so on....
...
1111111111111110000000000 up to here. The 3.268.760 member.

现在在一个矩阵为1×1，我必须有共同的15位跨越这些值。因为结果是> = 11它是一个有用的结果。

Now crossing these values over a matrix for the 1 x 1 I must have 15 bits common. Since the result is >= 11 it is a "useful" result.

对于1×2，我们有共同的所以也是一个有效的结果，14位。

For the 1 x 2 we have 14 bits common so also a valid result.

干这个的所有成员，最后，渡1个3.268.760应该产生5位共同如此，因为它是＆LT; 11它不是有用。

Doing that for all members, finally, crossing 1 x 3.268.760 should result in 5 bits common so since it's < 11 its not "useful".

我需要的是找出（由数学或算法）至极是成员的最小数量需要覆盖具有11位共同所有的可能性。

What I need is to find out (by math or algorithm) wich is the minimum number of members needed to cover all possibilities having 11 bits common.

在换言之基团N成员，如果测试对所有其他人可能有共同在整个3.268.760 x 3.268.760宇宙的至少11位。

In other words a group of N members that if tested against all others may have at least 11 bits common over the whole 3.268.760 x 3.268.760 universe.

使用蛮力算法，我发现，有81 25bit成员可能achive这一点。但我猜测，这个数字应该是较小的（东西接近12）。

Using a brute force algorithm I found out that with 81 25bit member is possible achive this. But i'm guessing that this number should be smaller (something near 12).

我试图用蛮力算法在3.268.760，使12个成员国所有可能的变化，但是可能性数目 它是如此的巨大，这将需要超过一百年来计算（3,156x10e69组合）。

I was trying to use a brute force algorithm to make all possible variations of 12 members over the 3.268.760 but the number of possibilities it's so huge that it would take more than a hundred years to compute (3,156x10e69 combinations).

我GOOGLE了关于组合学，但有这么多的领域，我不知道至极这些问题应该适合。

I've googled about combinatorics but there are so many fields that i don't know in wich these problem should fit.

因此​​在组合数学至极领域，或任何算法对这些问题的任何指示大大AP preciate。

So any directions on wich field of combinatorics, or any algorithm for these issue is greatly appreciate.

PS：仅供参考。两名成员的相似性的计算公式：

PS: Just for reference. The "likeness" of two members is calculated using:

(Not(a xor b)) and a

在，有一个小的递归循环计数比特给定共同的比特数。

After that there's a small recursive loop to count the bits given the number of common bits.

编辑：作为promissed（@btilly）下面这里的注释是关系的分形的形象或链接，图片

As promissed (@btilly)on the comment below here's the 'fractal' image of the relations or link to image

从红色（15bits比赛）色彩比例范围为绿色（11位匹配），以黑色为值，比10位更小。

The color scale ranges from red (15bits match) to green (11bits match) to black for values smaller than 10bits.

这图片是4096第一组只是样品。

This image is just sample of the 4096 first groups.

推荐答案

TL;博士：你想解决控制集在一个大的，非常对称图形。 btilly是正确的，你不应该期待一个确切的答案。如果这是我的问题，我会尝试本地搜索开始贪婪的解决方案。选择一组，并试图摆脱它通过改变别人。这要求数据结构以跟踪哪些套覆盖一次。

tl;dr: you want to solve dominating set on a large, extremely symmetric graph. btilly is right that you should not expect an exact answer. If this were my problem, I would try local search starting with the greedy solution. Pick one set and try to get rid of it by changing the others. This requires data structures to keep track of which sets are covered exactly once.

编辑：好的，这里是一个下界一个更好的主意。对于每k从1到最优解的值，有一个下限[25选择15] * K / [的k组最大接头覆盖。你势必12（实际上是10在我心目当中，因为你忘了一些邻居）对应于K = 1。证明素描：修正了一个任意的解决方案，M组，并认为可以用k的米中获得的最保险。构建一个小数解决方案，其中所选择的k的所有对称性进行平均，并调整，使得每个元件覆盖一次。这个解决方案的成本是[25选择15] *，这是至少一样大下界我们拍摄对于k / [那些k组最大接头覆盖。它仍然是至少为小，但是，由于原来的间设置的解决方案，由于每个组的边际回报正在下降。

Okay, here's a better idea for a lower bound. For every k from 1 to the value of the optimal solution, there's a lower bound of [25 choose 15] * k / [maximum joint coverage of k sets]. Your bound of 12 (actually 10 by my reckoning, since you forgot some neighbors) corresponds to k = 1. Proof sketch: fix an arbitrary solution with m sets and consider the most coverage that can be obtained by k of the m. Build a fractional solution where all symmetries of the chosen k are averaged together and scaled so that each element is covered once. The cost of this solution is [25 choose 15] * k / [maximum joint coverage of those k sets], which is at least as large as the lower bound we're shooting for. It's still at least as small, however, as the original m-set solution, as the marginal returns of each set are decreasing.

计算最大的覆盖范围是一般硬，但有一个因素（E /（E-1）） - 近似（≈1.58）算法：贪婪，这听起来好像你可以快速实施（注：你需要选择涵盖最破获另一台每次）设置。到了贪婪的解决方案，通过e乘以/（E-1），我们得到一个上界的最大覆盖k个元素，这足以供电下界在previous段落描述。

Computing maximum coverage is in general hard, but there's a factor (e/(e-1))-approximation (≈ 1.58) algorithm: greedy, which it sounds as though you could implement quickly (note: you need to choose the set that covers the most uncovered other sets each time). By multiplying the greedy solution by e/(e-1), we obtain an upper bound on the maximum coverage of k elements, which suffices to power the lower bound described in the previous paragraph.

警告：如果这个上限是大于[25选15]，则k过大

Warning: if this upper bound is larger than [25 choose 15], then k is too large!