计算一组数字的所有1-off组合

Question

北卡罗来纳州彩票提供了几种抽奖游戏，其中两种是Pick 3和Pick 4。您分别选择3或4位数字，介于0和9(包括0和9)之间，数字可以重复(例如，9-9-9是有效的组合)。对于这个例子，我将使用Pick 3，因为它更容易使用，但我试图使它成为一个通用的解决方案，可以处理任意数量的数字。

Pick 3和Pick 4的一个功能是"1-OFF“，这意味着如果您抽出的数字中至少有一个比您彩票上的数字高1或低1，您就会赢得奖品。

例如，假设你玩Pick 3，你为你的数字选择了5-5-5。至少有一个数字必须是1-off才能赢(因此，如果你这样玩游戏，5-5-5不会赢得任何奖品)。获胜组合将是：

1 Number    2 Numbers    3 Numbers
--------    ---------    ---------
4-5-5       4-4-5        4-4-4
5-4-5       5-4-4        6-6-6
5-5-4       4-5-4        4-4-6
6-5-5       6-6-5        4-6-6
5-6-5       5-6-6        4-6-4
5-5-6       6-5-6        6-4-4
            4-5-6        6-6-4
            6-5-4        6-4-6
            6-4-5
            5-6-4
            5-4-6
            4-6-5

(我认为这就是所有的组合，但您明白了)。

我能想到的最“有效”的解决方案是使用数组来定义哪些数字被更改，以及如何更改：

int[][] alterations = {
    // 1 digit
    {-1, 0, 0}, {0, -1, 0}, {0, 0, -1}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1},
    // 2 digits
    {-1, -1, 0}, ...
};

然后根据每个变更数组修改编号：

int[] numbers = {5, 5, 5};
for(int i = 0; i < alterations.length; i++) {
    int[] copy = Arrays.copyOf(numbers, numbers.length);
    for(int j = 0; j < alterations[i].length; j++) {
        // note: this logic does not account for the numbers 0 and 9:
        // 1 down from 0 translates to 9, and 1 up from 9 translates
        // to 0, but you get the gist of how this is supposed to work
        copy[j] += alterations[i][j];
    }
    printArray(copy);
}

...

private static void printArray(int[] a) {
    String x = "";
    for(int i : a)
        x += i + " ";

    System.out.println(x.trim());
}

但我想知道有没有更好的方法。有没有人遇到过这样的事情，并有更好的想法？

Answer 1

听起来像是在寻找回溯，因为构造变更数组相当单调乏味。在回溯算法中，您将构造候选对象，应用更改，并检查结果组合是否有效，如果是，则打印。我建议你阅读Steven Skiena的算法设计手册第7章，了解一些关于回溯的背景信息，以及如何使用组合问题来完成回溯。