这是一个更好的解决方案,灵感来自https://stackoverflow.com/a/10117424/312172 https://stackoverflow.com/a/10117424/312172
为了实现这一目标,我们不是得到一个混乱的元素列表,而是关注从列表中扣除元素时所做的选择。
给函数一个大小,以及一个小于阶乘(大小)的数字;它将返回我们需要做出的一系列选择才能获得排列。
例如:
getTheIndexOfSelection(100,5)-> 对于 5 个元素的列表,我们需要第 100 个排列。
它应该输出:[4,0,2,0,0]
这意味着,删除索引 4 处的元素,对于被删除的列表,删除 0 处的元素 ....
如果列表是[1,2,3,4,5];这将是采购:
[1,2,3,4,5] 删除索引 4 -> 5
[1,2,3,4] 删除索引 0 -> 1
[2,3,4] 删除索引 2 -> 4
[2,3] rovmove 索引 0 -> 2
[3] 删除索引 0 -> 3
我们按顺序删除的所有元素都是排列。
/**
* Feed this function a number, it gives you a sequence of choices
* to make a permutation.
* <br>
* if this return [0,0,0,0]
* it means remove element at 0, and then remove again... until
* reaches the end.
* @return
*
* @param
* len: the length of the list
* n: the number that got match to a certain permutation.
*/
public static int[] getTheIndexOfSelection(int n, int size)
{
int[] lst = new int[size];
return getTheIndexOfSelection( n, size, 0, lst);
}
private static int[] getTheIndexOfSelection(int n, int size, int index, int[] lst)
{
if(size==1)
{
int[] result = {0}; // a list of one element, you can only choose the one that is in it
// which is at index 0;
return result;
}
if(n >= factorial(size))return null; // This is not possible to do.
size-=1;
int firstchoice = n/factorial(size);
lst[index] = firstchoice;
n = n-firstchoice*factorial(size);
if(size>1)return getTheIndexOfSelection(n ,size, index+1, lst);
return lst;
}
这是一个更好的解决方案,因为:
- 速度实际上取决于阶乘函数,假设阶乘非常快,这将是 o(n)。
- 它将数字与排列相匹配,从而使映射和迭代器等可扩展。
- 这不是完整的解决方案,剩下要解决的部分现在几乎是微不足道的。