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

Question

我正在尝试解决以下问题。给定一个整数 n，列出所有 n 位数字，这样每个数字都没有重复的数字。例如，如果 n 为 4，则输出如下：012301240125...987598764 位数字的总数为 5040我目前的方法是蛮力。我可以生成所有 n 位数字，然后使用 Set 列出所有没有重复数字的数字。但是，我很确定有一种更快、更好、更优雅的方法来做到这一点。我在用 Java 编程，但我可以用 C 阅读源代码。

Answer 1

在数学上，你有10个所述第一数量，选项9为第二，8为第三，和7的第4位。所以，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 的评论中提取这一点，因为它说得很好，有助于澄清解决方案。

所以为了解释这里发生的事情 - 它正在递归一个带有三个参数的函数：我们已经使用过的数字列表（我们正在构建的字符串 - c），我们还没有使用过的数字列表（字符串r) 和目标深度或长度。然后当一个数字被使用时，它被添加到 c 并从 r 中删除以供后续递归调用，因此您不需要检查它是否已经使用，因为您只传递那些尚未使用的数字。

Answer 2

回溯法也是一种蛮力法。

private static int pickAndSet(byte[] used, int last) {

    if (last >= 0) used[last] = 0;

    int start = (last < 0) ? 0 : last + 1;

    for (int i = start; i < used.length; i++) {

        if (used[i] == 0) {

            used[i] = 1;

            return i;

        }

    }

    return -1;

}

public static int get_series(int n) {

    if (n < 1 || n > 10) return 0;

    byte[] used = new byte[10];

    int[] result = new int[n];

    char[] output = new char[n];

    int idx = 0;

    boolean dirForward = true;

    int count = 0;

    while (true) {

        result[idx] = pickAndSet(used, dirForward ? -1 : result[idx]);

    if (result[idx] < 0) {  //fail, should rewind.

      if (idx == 0) break;      //the zero index rewind failed， think all over.

      dirForward = false;

      idx --;

      continue;

    } else {//forward.

        dirForward = true;

    }

    idx ++;

    if (n == idx) {

        for (int k = 0; k < result.length; k++) output[k] = (char)('0' + result[k]);

        System.out.println(output);

        count ++;

        dirForward = false;

        idx --;

    }

    }

    return count;

}

Answer 3

注意这里的对称性：

0123

0124

...

9875

9876

9876 = 9999 - 123

9875 = 9999 - 124

所以对于初学者来说，你可以把工作切成两半。

您可能能够找到一个涵盖场景的正则表达式，例如，如果一个数字在同一字符串中出现两次，则它匹配/失败。

正则表达式是否会更快，谁知道呢？

特别是对于四位数字，您可以嵌套 For 循环：

for (int i = 0; i < 10; i++) {

   for (int j = 0; j < 10; j++) {

       if (j != i) {

           for (int k = 0; k < 10; k++) {

               if ((k != j) && (k != i)) {

                   for (int m = 0; m < 10; m++) {

                       if ((m != k) && (m != j) && (m != i)) {

                           someStringCollection.add((((("" + i) + j) + k) + m));

（等等）

或者，对于更通用的解决方案，这是递归的方便性的一个很好的例子。例如，您有一个函数，它获取先前数字的列表和所需的深度，如果所需数字的数量小于深度，则只需进行十次迭代的循环（通过您要添加的数字的每个值），如果该数字已不存在于列表中，然后将其添加到列表中并递归。如果您处于正确的深度，只需连接列表中的所有数字并将其添加到您拥有的有效字符串集合中。