java - 给定一个数字 n，列出所有 n 位数字，使得每个数字都没有重复数字

Question

我正在尝试解决以下问题。给定一个整数 n，列出所有 n 位数字，使得每个数字都没有重复数字。

例如n为4，则输出如下:

0123
0124
0125
...
9875
9876
Total number of 4-digit numbers is 5040

我目前的方法是蛮力。我可以生成所有 n 位数字，然后使用 Set 列出所有没有重复数字的数字。不过，我很确定有一种更快、更好、更优雅的方法可以做到这一点。

我用 Java 编程，但我可以用 C 阅读源代码。

谢谢

Answer 1

从数学上讲，第一个数字有 10 个选项，第二个有 9 个，第三个有 8 个，7 个 第四次。所以，10 * 9 * 8 * 7 = 5040。

以编程方式，您可以使用一些组合逻辑生成这些。使用函数式方法通常可以使代码更简洁；这意味着递归地构建一个新字符串，而不是尝试使用 StringBuilder 或数组来不断修改现有字符串。

示例代码

以下代码将生成排列，无需重复使用数字，无需任何额外的集合或映射等。

public class LockerNumberNoRepeats {
    public static void main(String[] args) {
        System.out.println("Total combinations = " + permutations(4));
    }

    public static int permutations(int targetLength) {
        return permutations("", "0123456789", targetLength);
    }

    private static int permutations(String c, String r, int targetLength) {
        if (c.length() == targetLength) {
            System.out.println(c);
            return 1;
        }

        int sum = 0;
        for (int i = 0; i < r.length(); ++i) {
            sum += permutations(c + r.charAt(i), r.substring(0,i) + r.substring(i + 1), targetLength);
        }
        return sum;
    }
}

输出:

...
9875
9876
Total combinations = 5040

解释

从 @Rick 的评论中提取这个，因为它说得很好，有助于澄清解决方案。

So to explain what is happening here - it's recursing a function which takes three parameters: a list of digits we've already used (the string we're building - c), a list of digits we haven't used yet (the string r) and the target depth or length. Then when a digit is used, it is added to c and removed from r for subsequent recursive calls, so you don't need to check if it is already used, because you only pass in those which haven't already been used.