Java中某些数字的排列

Question

我意识到编程语言中的排列是一个非常常见的问题，但是我觉得我的问题是独一无二的。

我收到了一定长度的整数N的输入，并将每个数字存储在一个数组中，该数组的索引存储了该数字在N中出现的次数。

现在，我想测试某个函数是否对没有前导零的N的原始长度的所有排列都成立。例如：

int[] digits = new int[10];
String n = "12345675533789025";
for (char c : n.toCharArray())
    digits[c-'0']++;
for (Long f : allPermutationsOf(digits))
    if (someCondition(f))
        System.out.println(f);

以下代码的前提条件是N必须小于2^64-1 (long的最大值。)

问题是，我如何获取数字数组的所有排列并返回一个Long[]或long[]，而不使用某种String连接？有没有办法返回一个包含digits[]在“整型作用域”中的所有排列的long[]，或者更确切地说，只使用整型算法？

Answer 1

为了详细说明上面的注释之一，将数字d放在结果long中的给定位置很容易：d*1将其放在1的位置，d*1000将其放在千位，通常d * (10^k)将d放入k+1th数字。总共有N个数字需要填充，因此需要对10的幂进行从1到10^(N-1)的排列。

Answer 2

如果您希望排列是Longs，而不是将n表示为计数数组，那么将其表示为Long也可能更容易。

以下是生成排列的几种方法。

1. 将生成排列看作是查找具有相同数字集的下一个最大数字，从由n的排序数字组成的数字开始。在这种情况下，this StackOverflow question的答案很有帮助。您可以使用算术运算和修改，而不是字符串连接来实现算法(如果您愿意，我可以提供更多细节)。这样做的一个好处是，您生成的排列将自动按顺序排列。
2. 如果您不关心排列的顺序，并且希望数字重复的数量很小，那么您可以使用Steinhaus-Johnson-Trotter算法，根据Robert Sedgewick的说法，这是生成唯一元素排列的最快算法。为了确保不会生成重复的排列，您必须区分每个重复的数字，并仅在它们按顺序出现时发出排列(即，如果2出现三次，则创建元素2_1、2_2和2_3，并确保这三个元素始终以该顺序出现在发出的permutation).

中

Answer 3

对于这个要求，假设N的长度是n，我们可以通过从0到n- 1从一个数字到另一个数字来生成所有的排列，其中0是前导数字。

对于每个数字，我们只检查一次每个可能性(0到9)，这将避免重复排列。

从数字x到数字x+ 1，我们可以通过传递一个名为current的数字轻松地生成当前值

例如:在数字3，我们有电流= 1234，所以在数字4，如果我们选择5在数字4，电流将是1234*10 +5= 12345

Java中的示例代码：

public void generate(int index, int length, int[] digits, long current, ArrayList<Long> result) {
    //All the permutation will be stored in result ArrayList
    for (int i = 0; i < 10; i++) {
        if (digits[i] > 0 && (i != 0 || index != 0)) {                
            digits[i]--;
            if (index + 1 == length) {//If this is the last digit, add its value into result
                result.add(current * 10 + i);
            } else {//else, go to next digit
                generate(index + 1, length, digits, current * 10 + i, result);
            }
            digits[i]++;
        }
    }
}