如何从 n 位数字中得到 n/2-digit 组合

Question

我正在为这个算法苦苦挣扎。它应该像这样工作：

如果我输入f.e。 6880，我的程序应该输出 80 86 80 86 60 68 68.

如您所见，组合在重复。那是因为它会查看每个数字，因为它是一个不同的对象。 在我的程序中它是正确的。

这是我的代码：

public static Set<Integer> get2DCombinations(List<Integer> digits) {
    Set<Integer> combinations = new TreeSet<>();

    int t = 0;
    for(Integer i : digits) {
        for (Integer j : digits) {
            t = i * 10 + j;
            if (t / 10 >= 1) {
                combinations.add(t);
            }
        }
    }

    return combinations;
}

它returns一组特定的组合，其中所有组合都有 2 个数字。

它工作得很好，但只适用于 4 位数字。当然，我可以再使用一个 for-each 循环，但是有没有办法让它自动化？

因此，如果我输入 6 位数字，它应该输出所有可能的 3 位数字组合，如果我输入 8 位数字，它应该输出所有可能的 4 位数字组合。 输入数字的位数总是偶数。

你能告诉我怎么做吗？

Answer 1

先尝试计算 n / 2。所以，如果 n 是 6，那么 n / 2 = 3。那么在开始计算组合之前你就知道你正在寻找 3 位数字的组合。然后你想找到正确的算法来找到组合。解决问题的一部分是将问题分解为更小的问题。这就是我在这里所做的。但是我没法帮你解决，因为你自己解决比较好，其次，你没有提供细节，很难给出正确的解决方案。

Answer 2

您需要一个递归程序来为您的输入生成所有组合。这是我的解决方案。我的方法接受一个 String 作为输入（它只是一个简短的程序，更容易，你可以根据你的需要调整它）：

public static Set<String> get2DCombinations(String input) {
    return backtracking("", input, input.length() / 2) ;
}

public static Set<String> backtracking(String actual, String remaining, int length) {
    if (actual.length() == length) {
        return new HashSet<>(Arrays.asList(actual));
    }

    Set<String> result = new HashSet<>();
    for(int i = 0; i < remaining.length(); i++) {
        result.addAll(backtracking(actual + remaining.charAt(i), remaining.substring(0, i) + remaining.substring(i + 1), length));
    }
    return result;
}

然后你像这样调用方法：

System.out.println(get2DCombinations(input));

结果：

[88, 68, 06, 80, 08, 60, 86]

正如我在评论中提到的，您缺少一些组合。此解决方案生成所有这些。

如何从 n 位数字中得到 n/2-digit 组合

How to get n/2-digit combinations from n digit number

java

combinations

combinatorics