java - 允许重复时如何获得第n个排列？

Question

欧拉计划 24:数字 0、1、2、3、4、5、6、7、8 和 9 的百万分之一字典排列是什么？

如果允许重复怎么办？像 1111111111、1223344457 等。如何获得百万次排列，其中重复也包括在计数中。

请注意，输入仍然是相同的。输入无重复。

我想生成所有可能的长度为 10 的密码。密码可以包含重复的字符，所以我希望我的函数也适用于此。

这是给出字符串第 n 次排列的代码。它的工作原理是利用 n 个元素有 n!排列。并在字典序排列中排在第一位 (n-1)!排列将从第一个数字开始，依此类推。

我如何修改它以获取重复的字符串？我应该使用什么特定的算法？

为了澄清事情，我不仅需要百万分之一的排列。我需要所有可能的排列。通过在此函数上运行 for 循环，我可以获得所有排列而不重复。但我无法通过重复获得排列。我想要重复排列。因为我想获得所有可能的密码。想一想如果只允许使用数字，您可以拥有 10 个字母的所有可能密码。 10^10。我想要所有的。

import java.util.*;

public class NthPermutation{

    private static int Factorial(int n){  
        if (n < 0)
            return 0;
         int ans = 1;
         for (int i=1;i<=n;++i)
            ans *= i;
         return ans;
     }

     public static String getNth(List<Integer> original, int permNum){

         List<Integer> numbers = new ArrayList<Integer>(original);  
         String nth = "";
         permNum--;
         int N = numbers.size();  

         for (int i=1;i<N;++i){
             int j = permNum / Factorial(N - i); 
             permNum = permNum % Factorial(N - i);
             nth = nth + numbers.get(j);
             numbers.remove(j);

         if (permNum==0)
             break;
         }

         for (int i=0; i<numbers.size();i++)
             nth = nth + numbers.get(i);

         return nth;
      }

      public static void main(String[] args){

          List<Integer> numbers = new ArrayList<Integer>();     
          for (int i = 0; i < 10; i++) 
              numbers.add(i);

          System.out.println(getNth(numbers,1000000)); 
       }
}

Answer 1

如果允许重复，则:

• 第一个排列是0000000000
• 第二个排列是0000000001
• 第十个排列是0000000009
• 第一百次排列是0000000099
• 千次排列是0000000999
• 百万次排列是0000999999

等等。

所有这些都只是数字 n-1在左侧填充足够数量的零，使整个字符串的长度为 10。

因此，要获得实际的第 n 个组合，您所要做的就是(在 Python 代码段下方，您可以轻松转换为 Java):

>>> def find_nth_combination(n):
...     print "0" * (10-len(str(n-1))) + str(n-1)
... 
>>> find_nth_combination(1)
0000000000
>>> find_nth_combination(100)
0000000099
>>> find_nth_combination(9062300000)
9062299999
>>> find_nth_combination(12300000)
0012299999

如果你想通过重复来解决这个问题，你可以have a look here (代码在 Python 中)。

---

要获得所有排列，只需遍历所有数字即可。

因此，您需要执行以下操作:

for x in xrange(1, 1001):
    find_nth_combination(x)

将输出:

0000000000
0000000001
...
...
0000000997
0000000998
0000000999