-
1772池就是把双色球所有开奖序列排列组合出来，给所有人平均分配。
-
这样无论如何不会产生漏奖的情况。
-
但是也存在问题。就是排列组合的数据量太大，17721088种排列组合，要做到给火星用户平均分配一下，还是需要非常大计算量的。
-
并且存储量也是非常大的。排列组合总体保存17721088种，就需要大约1G的内存空间。想要做到优化，还不能给用户表中直接保存号码组合，可以保存一个数字。数字代表了他分到的号码组合在17721088种组合中的位置。
-
但是这样一来，兑奖的时候就比较麻烦，我们需要把所有用户的所有排列组合查询出来，挨个兑奖，看看中了几个红球，几个蓝球。但是这个查询过程很麻烦，因为数据量特别大，数据库也会有很大的压力。
-
所以这时候，可以用到康托展开公式。
-
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的名次，因此是可逆的。
-
**X = A[0] * (n-1)! + A[1] * (n-2)! + … + A[n-1] * 0! **
A[i] 指的是位于位置i后面的数小于A[i]值的个数,后面乘的就是后面还有多少个数的阶乘
说明 ：这个算出来的数康拖展开值，是在所有排列次序 - 1的值，因此X+1即为在全排列中的次序 -
但是双色球的开奖，属于组合，不属于排列。所以康托展开需要做一些变换。
-
我们把33个红球，用1表示选中，用0表示未选中，做成一个33位的字符串，用来表示一注号码。比如：111111000000000000000000000000000表示开奖号码为1，2，3，4，5，6的红球组合。
-
把这个33位的字符串，当成一个二进制数字来看。这样，比较大小就很容易了。最高位是1的，肯定比最高位是0的大。最高位都是1的，就比较下一位。
-
按照这个顺序进行排序。得到的排序是唯一的。既然顺序唯一，序号和组合，就可以完全一一对应起来。
-
所以任何一个方案的序号的表达形式，都可以认为是比它小的所有的数字的数量。
-
所以就可以理解为，将每一位号码从1置换为0之后，右侧部分的排列组合。所以这个数量也就可以比较简单的计算出来了。
-
$f("0...0")=\sum_MC_{p[i]}$其中 $p[i]$表示第i个1在整个序列中的位置(从右向左)。例如：1011000(太多了，就不用33位了)，第一个1，从右向左数，是第p[1]=4位，第二个1，第p[2]=5位，第3个1，第p[3]=7位。它在整体7位数选取3位的组合中（$C_73$）的排序位置是：$C_41+C_52+C_73=49$
-
反向通过序号查找序列的方法也可以安排了。因为从左边开始，第1个1的位置，就是比他小的所有数字排列组合的数量。$C_pm$,下一位，以此类推。查找第一个位置，就是要找到这个1在这个数字中的位置p。比如你要查找第n位，只需要找到一个合适的p，使得$C_pm<=n$并且$C_{p+1}^m>n$即可。
-
上代码：
/// 获取红球的序号第X个，自然数，从1开始。28,29,30,31,32,33 = 1
// 1,2,3,4,5,6 = 1107568
private static int getRedIndex(int[] redBalls) {
int total = 0;
int base = 6;
// 从高位开始。
for (int ball : redBalls) {
int pos = 33 - ball;
long compute = AlgorithmicUtils.C(pos, base--);
compute = compute < 0 ? 0 : compute;
total += compute;
}
return total + 1;
}
/**
* 通过制定的序号，查找1772池对应的方案组合。
* 序号取值范围是：1-17721088.自然数
*
* @return 返回一个格式化好的号码方案：01,02,03,04,05,06#01
*/
public static String getPlan(int index) {
// 规则判定
if (index < 1 || index > 17721088) {
return null;
}
// 蓝球在序列中的序号
int blue = index % 16;
// 计算完毕之后，再将蓝球转换为合法的数字
if (blue == 0) {
blue = 16;
}
// 红球在序列中的序号，第XX个，自然数。从1开始
int redIndex = index / 16 + (index % 16 > 0 ? 1 : 0);
// 修改为序列中的逻辑序号，从0开始。
redIndex = redIndex - 1;
// 查找红球。
int[] reds = new int[6];
for (int i = 0; i < 6; i++) {
int base = 6 - i;
for (int j = 0; j < 33; j++) {
long tmp = AlgorithmicUtils.C(j, base);
int km = (int) (tmp < 0 ? 0 : tmp);
tmp = AlgorithmicUtils.C(j + 1, base);
int kp1m = (int) (tmp < 0 ? 0 : tmp);
if (redIndex >= km && redIndex < kp1m) {
reds[i] = 33 - j;
redIndex = redIndex - km;
break;
}
}
}
// 格式化方案
return formatPlan(reds, blue);
}
评论区