允许重复时如何获得第 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

如果你想通过重复来解决这个问题，你可以看看这里（代码是Python）。

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

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

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

这将输出：

0000000000
0000000001
...
...
0000000997
0000000998
0000000999