给定数字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的评论中得出这个，因为它很好地说，并有助于澄清解决方案。

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

Answer 2

很容易找到一个公式。即

如果n=1有10变种。

如果n=2有9*10变种。

如果n=3有8*9*10变种。

如果n=4有7*8*9*10变种。

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));

（等等）

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

Answer 4

回溯方法也是一种蛮力方法。

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;
}