Project Euler 24: 按字典顺序排列的数字0、1、2、3、4、5、6、7、8和9的第100万个排列是什么?
如果允许重复,如1111111111
,1223344457
等,我该如何获得包括重复在内的第100万个排列。
请注意,输入仍然相同。输入中没有重复。
我想生成长度为10的所有可能密码。密码可以包含重复字符,因此我希望我的函数也适用于这种情况。
以下是一个给出字符串的第n个排列的代码。它利用了这样一个事实:对于n个元素,有n!种排列。在字典排序的排列中,前(n-1)!个排列以第一个数字开头,依此类推。
我该如何修改这个代码来获得包含重复字符的字符串?是否有任何特定的算法可以使用?
澄清一下,我不仅需要第100万个排列。我需要所有可能的排列。我可以通过在此函数上运行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));
}
}
[1,1,2,3]
尝试了您的程序:排列 #1 输出1,1,2,3
;排列 #2 输出1,1,3,2
;排列 #24 输出3,2,1,1
。 - גלעד ברקן