允许重复时如何获得第n个排列? [英] How to get nth permutation when repetition is allowed?
问题描述
欧拉项目24:数字0、1、2、3、4、5、6、7、8和9的百万分之一的词典编排是什么?
Project Euler 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
如果允许重复怎么办?像1111111111，1223344457等.如何获得百万分之一的排列，其中重复也包括在计数中.
What if repetitions are allowed? like 1111111111,1223344457 etc. How can I get millionth permutation where repetitions are also included in counting.
并且请注意，输入将仍然是相同的.输入中没有重复.
And please note that input would still be the same. No repetitions in input.
我想生成所有可能的长度为10的密码，并且密码可以包含重复的字符，因此我也希望我的功能也能起作用.
I want to generate all possible passwords of length 10. And passwords can contain repeated characters so I want my function to work for that too.
这是给出字符串第n个排列的代码.它通过利用n个元素中存在n个元素的事实而起作用.排列.并且在字典编排中首先(n-1)！排列将从第一个数字开始，依此类推.
Here is the code which gives nth permutation of a string. It works by exploiting the fact that for n elements there are n! permutations. And in lexicographic permutation first (n-1)! permutations would start with first digit and so on.
我该如何修改它以获取具有重复的字符串?我应该使用任何特定的算法吗?
How can I modify this to get strings with repetitions also? Any particular algorithm which I should use?
为了澄清问题，我不仅需要百万分之一的排列.我需要所有可能的排列.通过在此函数上运行for循环，我可以获得所有排列而无需重复.但是我无法得到重复的排列.我想要重复排列.由于我想获得所有可能的密码.如果只允许输入数字，请考虑一下您可能拥有的10个字母的所有密码. 10 ^ 10.我要所有人
To clarify things, I don't only need millionth permutation. I need all possible permutations. I can get all permutations without repetitions by running a for loop on this function. But I can't get permutations with repetitions. I want permutations with repetitions. Since I want to get all possible passwords. Think of all the possible passwords that you can have of 10 letters if only numbers were allowed. 10^10. I want all of them.
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));
}
}
推荐答案
如果允许重复，则:
- 第一个排列是
0000000000 - 第二个排列是
0000000001 - 第十个排列是
0000000009 - 百分位数是
0000000099 - 千分之一排列是
0000000999 - 百万分之一排列是
0000999999
- the first permutation is
0000000000 - the second permutation is
0000000001 - the tenth permutation is
0000000009 - the hundredth permutation is
0000000099 - the thousandth permutation is
0000000999 - the millionth permutation is
0000999999
以此类推.
所有这些都是简单的数字n-1，左侧填充了足够数量的零，以使整个字符串的长度为10.
All of these are simply the number n-1 padded with enough number of zeroes on the left to make the whole string of length 10.
因此，要获得实际的第n个组合，您所需要做的就是(在Python的代码段下面，您可以轻松地转换为Java):
So to get the actual nth combination, all you would have to do is (below snippet in Python, you can convert to Java easily):
>>> 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中).
In case you want to solve this with repetition, you can have a look here (code is in Python).
要获得所有排列，只需遍历所有数字即可.
To get all permutations, simply go through all the numbers.
因此，您将需要执行以下操作:
So, you will need to do something like:
for x in xrange(1, 1001):
find_nth_combination(x)
它将输出:
0000000000
0000000001
...
...
0000000997
0000000998
0000000999
这篇关于允许重复时如何获得第n个排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
