java - 有没有办法计算嵌套 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 可以被视为 Combinatorial number system 中的一个数字, 其中循环变量 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 的额外静态内存。