有没有办法计算嵌套for循环生成的索引？

Question

我目前正在考虑如何存储经常访问的数据.它意味着存储在一个数组中,目前通过以下方式生成.

public static void generateData() {

    int index = 0;
    for(int a1 = 0; a1 < 52; a1++) {
        for(int a2 = a1 + 1; a2 < 52; a2++) {
            for(int a3 = a2 + 1; a3 < 52; a3++) {
                for(int a4 = a3 + 1; a4 < 52; a4++) {
                    for(int a5 = a4 + 1; a5 < 52; a5++) {
                        for(int a6 = a5 + 1; a6 < 52; a6++) {
                            for(int a7 = a6 + 1; a7 < 52; a7++) {
                                data[index++] = compute(a1,a2,a3,a4,a5,a6,a7);
                            }
                        }
                    }
                }
            }
        }
    }
}

我现在的问题是使用a1到a7参数快速访问计算数据.我能想到的唯一方法是迭代类似于迭代时间,直到参数相同,就像这样

public static int getIndex(int i1, int i2, int i3, int i4, int i5, int i6, int i7) {
    int index = 0;
    for(int a1 = 0; a1 < 52; a1++) {
        for(int a2 = a1 + 1; a2 < 52; a2++) {
            for(int a3 = a2 + 1; a3 < 52; a3++) {
                for(int a4 = a3 + 1; a4 < 52; a4++) {
                    for(int a5 = a4 + 1; a5 < 52; a5++) {
                        for(int a6 = a5 + 1; a6 < 52; a6++) {
                            for(int a7 = a6 + 1; a7 < 52; a7++) {

                                if(a1 == i1 && a2 == i2 && a3 == i3 && a4 == i4 && a5 == i5 && a6 == i6 && a7 == i7) {
                                    return index;
                                } else {
                                    index++;
                                }

                            }
                        }
                    }
                }
            }
        }
    }

    throw new IllegalArgumentException();
}

然而,这种方法仅在线性时间运行,考虑到数据量,这不够快.因此,我想知道是否有任何方法可以在常数或对数时间内计算指数.因为我的问题似乎很模糊.我正在存储每个可能的Texas hold'em手的所有可能结果,以进行进一步的测试.

Answer 1

在您的情况下,index可以将其视为组合数系统中的数字,其中循环变量a1... a7是此数字的数字.

这是一个从给定的循环变量计算索引的函数.

public static int getIndex(int a1, int a2, int a3, int a4, int a5, int a6, int a7) {
    return 133784559 - (C7[a1] + C6[a2] + C5[a3] + C4[a4] + C3[a5] + C2[a6] + (51 - a7));
}

static final int[] C2 = Ck(2), C3 = Ck(3), C4 = Ck(4), C5 = Ck(5), C6 = Ck(6), C7 = Ck(7);

// Creates a cache of C(51-i, k) for 0 <= i < 52
static int[] Ck(int k) {
    int[] result = new int[52];
    for (int i = 0; i < 52; i++) {
        result[i] = (int) C(51 - i, k);
    }
    return result;
}

// Computes binomial coefficient C(n, k)
static long C(int n, int k) {
    long C = 1;
    for (int i = 0; i < k; i++) {
        C = C * (n - i) / (i + 1);
    }
    return C;
}

getIndex 方法非常快,只需要大约1K的额外静态内存.