主题：如何分摊秘密（一）——从《鹿鼎记》中的四十二章经说起 -- 明日枯荷包

也能够理解

按需要消化消化的是为何这两种合理的方法相差一个数量，相差一个怎样的数量

我想m兄的C（m-1,N)和您的C（m，n)相差一个数量的原因是钥匙可以有不同，但是我得再想想

自己没想明白的东西，真称不上懂，呵呵，不过我想您已经给我指出方向了

相差一个数量的原因，我前面说了，其实是锁的结构不同。我的锁是多钥锁，但每把钥匙都不同。M兄的锁是单钥锁，但是允许有多把相同的钥匙。

M兄的方法应该这么理解：对于任何一个m-1人组，我们要有一只“禁制锁”，除了这m-1人外，其他(n-m+1)人都能开这锁。这样一共有C(m-1,n)只禁制锁，它们都并联地锁在门上。

任何m-1个人的话，都有一只对付他们的禁制锁，所以那只锁他们是开不了的。但是只要有m人，无论哪只禁制锁都只最多能对付其中的m-1人（有些锁说不定这m个人里有好几个都有钥匙）于是一定能开。

如果考虑总共8人如3人可开门的情况。我的方法是弄C(3,8)只3钥锁串在一起，而M兄的方法弄C(2,8)只禁制锁并联来一起，每锁有8-2=6把钥匙。

所以我前面的说法有问题，我开始以为可以统一成“一锁一钥”的串联并联法。事实上我们的方法并不等价，一个是先并后串（多钥一起才能开锁可以看成是一锁一钥的并），一个是先串后并（多钥每钥都可单独开锁可以看成一锁一钥的串）。不过这两种方法的钥匙数量总是相同的，就是truth兄底下说的C(m-1,n)*(n-m+1) = C(m-1,n-1)*n = C(m,n)*m。等式左边是M兄的方法，右边是我的方法。不过我相信还是有某种转换的理解方式可以统一这两种方法。

没有疑惑了！

解惑又得宝，兄真是我的贵人！

C(m-1,N)等价于在N人中最多的人到场不能解密的组合

C(m,N)等价于在N人中最少的人到场必能解密的组合

这是一个问题的两个方面。

按兄的并联再串联法，两组并联锁记为：

A1，A2。。。Am

B1，B2。。。Bm

Am和Bm的多钥锁是可以相同的，A1...Am或者B1...Bm的并联内部的钥匙不同。简化点说，只要把秘密分成M份，然后，再在N人中的任选M人中分配，共分配C（m,N)组，也可以达到至少M人到场才能解密的结果，也就是说对应“密码”只要M个，不需要C（m,n)*m个。不知兄以为然否？

按我的并联再串联法，多钥锁的数量是C(m,n)个而不是m个啊。

我本来想您的方法也可看作将秘密分成M份，然后对N人中分配C(m,n)次，所以，从这个角度看，A1,B1,C1....是同一信息的不同表述，所以我在想是否有必要不一样。但是必须得不一样，否则C(m,n)把锁就相当于一把锁了，比较荒谬的错误。烦扰。

刚刚看到了楼主的帖子，很受启发，看来我还得花些时间，慢慢消化。

现在我正好有一个工作中的问题，没有太多头绪，我想这个与密码学有联系，想请楼主不吝指教：

现在有十万种商品，都已编码，标准是九位数字：999-99-9999（前三位是部，中间两位是类，后面四位是项， 让我们用英文字母，D-C-I来代表）。

D的取值范围是 002-300，C：00-99 I：0001-9999.

现在，我们要在这十万种商品抽取若干种（1 到 30 种）。我要给这每一种抽法，编一个唯一的代码。要如何入手？

最直观的办法当然是，先排序，然后拼接在一起。但是这样太占空间，意味着代码长度达到9×30=270字节。（如果不足30 种，用0填充）。

有没有一种比较简单的算法，产生唯一的编码，而且长度控制在20字节以内（当然更少就更好）？我们放宽条件：产生的编码可以是串string（字母与数字混合）？

我自己初步设想是，先计算抽取的商品种类数目（比如抽12种，就用12作为编码的一部分），然后再与这12种商品编码的均值拼接，这样11 个字节就够了，但这样，“撞码”的几率较大？

如果只有10万种商品，但是希望尽量减少编码的字节，那么应该把这种商品编码转换成内部编码，从0到999999编号。如果不愿意做这个转换，那么下面的100000都要换成1000000000。

如果说允许撞码，只是希望撞码可能性小一点，那么这就是希望找一个好的哈希函数（也叫杂凑函数）。象你这样取平均值也是一种哈希函数，但是效果显然不好，因为那些比较大和比较小的编码没有比较中间那些编码容易被取到。我觉得取加起来再除以100000的余数来做编码（再拿抽取的数目拼接也可以），要比平均值好，因为它的“撞码率”均匀。而且这个方法也容易扩张，如果你还想缩短字节数，可以除以10000，如果觉得字节数长一些也没关系，那么就除以更大的数。

如果说不允许撞码，那么代码长度不可能小于log(100000^30/30!)，也就是差不多150-log(30!)，大约是117字节左右。

可以把产品码当作一个数字，比如最大的一个产品码是300999999，最小的一个产品码是002000001。

制定编码规则如下：把数字0-9，A-Z，a-z依次编码成0-61共62个码，每个数字对应一个字符，比如数字0对应字符0，数字26对应字符a。。。数字61对应字符Z

把产品码300999999除以62，得到整数XXX1和余数YYY1=43，记录YYY1；

继续把XXX1除以62，得到整数XXX2和余数YYY2，记录YYY2=52；

。。。59；

。。。22；

最后直到整数为0，余数小于62，记为YYYn=20

所以把所有余数按倒序排起来，即20，22，59，52，43。按照前面说的编码规则编成5个字符，我偷个懒就不对应了。这就是产品的编码。

解码的时候这么做：

首先把编码字符还原成0-61的数字串20，22，59，52，43。

第一个数字20，乘以62，得到ZZZ1；

第二个数字22+ZZZ1，得数再乘以62，得到ZZZ2；

第三个数字59+ZZZ2，得数再乘以62，得到ZZZ3；

第四个数字52+ZZZ3，得数再乘以62，得到ZZZ4；

第五个数字43+ZZZ4，即可得到原来的产品码300999999。

照此办理，把最小的产品码的编码计算出来。如果你的产品码都是连续的，那么有效抽法编码范围就在最小产品码与最大产品码之间，并且由于编码时是按照ASCII值的顺序，所以可以简单地用字符串比较的方法来验证随意生成的编码是否有效码了。

可惜的是你的产品码I的取值不包括0000，所以不够连续。只能先解码出产品码，再验证是否有效的产品码，如果无效的话就重新产生了。好在I取值0000的机会只有万分之一，所以在最小编码与最大编码之间随意产生的编码的有效率应该是9999/10000，成功率是很高的。考虑到有的产品码没有对应有效的产品（无效的产品码），所以只能解出产品码后再对照产品库的编码，确定这是否有效码了。

连续生成30个有效的5位产品编码，得到5×30个字符的抽取码。

+++++补充++++++

改进一下，编码规则里取消0。即用数字1-9,A-Z,a-z依次编成61个码。以后编码解码的时候都乘以或者除以61。这样产品编码长度仍然是5位，但是当只取12个产品的时候，其余30-12=18个产品码就可以用18个单独的0来表示。所以取12个产品的时候，抽取码长度是5*12+18=78位。

恭喜：你意外获得【铢钱】八个

鲜花已成功送出，消耗 铢钱 1 个，可能得宝。可通过工具取消

提示：此次送花为【有效送花赞扬，加乐善、声望、帖得花总数】。

楼主与你的办法都很有道理。

我发现在问题的实际处理中，我只需要确保同一次运算中，不出现撞码即可，两三千家商店总共只有最多百来种抽法，我编码目的是正确地将商店按抽法分组。所以HASH算法可能就够了。

但是我最终还是采用拼接法，因为它在编程上最简单。我只要将商店码与拼接码写入一个临时数据库的TABLE，就很容易产生分组码了，最多只要三字节。两三千条记录的TABLE对数据库系统是小意思。后面的复杂运算就采用这个三字节码即可。最后，再从临时TABLE调回实际的商品种类。这样也能避免运算过程中，长码造成的资源浪费。

谢谢楼主接纳

之前误操作了，没写完就提交了

不过因祸得福，自己把问题想明白了

很简单，把每个产品码当做一个整数就是了。 最大的是300-99-9999， 完全可表达为一个4字节的整数。

排序好后按你的想法并列一下就是抽样的代码。30个数120个字节。

计算机里最少要64个字节表达30个1--10万的数。算法恐怕就太麻烦了。