算法讨论：已知一个排列在其按字典顺序的全排列中的序号，求该排列

好吧，承认标题有点绕，文字不太好描述，还是举例吧，

比如我们知道字符串1234的全排列有4！=24种，把24种排列按字典顺序排列如下：

1234 1

1243 2

1324 3

1342 4

1423 5

1432 6

2134 7

2143 8

2314 9

2341 10

2413 11

2431 12

3124 13

3142 14

3214 15

3241 16

3412 17

3421 18

4123 19

4132 20

4213 21

4231 22

4312 23

4321 24

那么问题来了，求某算法或思路，满足根据序号求排列，

比如给出20,怎么得出4132，给出13，怎么得出3124

解答如下：

 

public class ChoiceDict {

public static void main(String[] args) {

ChoiceDict a = new ChoiceDict();

int count = 4;//输入元素个数按照 1234

int choice=13;

int[] p = new int[count];

for (int i = 1; i <= p.length; i++) {

p[i - 1] = i;

}

boolean con;

// long start=System.currentTimeMillis();

do {

if(choice--==0)

a.pr(p);// 输出排列

con = a.next(p);// 求出按字典序排列的下一个排列p

} while (con);

//System.out.println(System.currentTimeMillis()-start);

}

public int indexof(int[] n) {

int index = -1;

for (int i = n.length - 1; i >= 1; i--) {

if (n[i - 1] < n[i]) {

index = i - 1;

break;

}

}

return index;

}

public int indexmin(int ini, int[] n) {

int index = n.length - 1;

int min = n[ini + 1];

for (int i = ini + 1; i < n.length; i++) {

if (n[i] <= min && n[i] > n[ini]) {

min = n[i];

index = i;

}

}

return index;

}

public void swap(int index1, int index2, int[] n) {

int temp;

temp = n[index1];

n[index1] = n[index2];

n[index2] = temp;

}

public void oppositeDirection(int index1, int[] n) {

for (int i = index1 + 1, j = n.length - 1, k = 0, temp; k <= (n.length - i) / 2; i++, j--, k++) {

temp = n[i];

n[i] = n[j];

n[j] = temp;

}

}

public boolean next(int[] n) {

int index1 = indexof(n);

if (index1 == -1) {

return false;

}

int index2 = indexmin(index1, n);

swap(index1, index2, n);

oppositeDirection(index1, n);

return true;

}

public void pr(int[] n) {

for (int i = 0; i < n.length; i++) {

System.out.print(n[i] + " ");

}

System.out.println();

}

}

js实现方法

getNum(bits, index)

1. 0 < bits < 10

2. index > 0

3. 所有不合理的结果都返回　-1

example:

getNum(4, 2);

getNum(5, 11);

在浏览器控制台 即可测试

function getNum(bits, index)

{

if(index <= 0 || bits < 1 || bits > 9)

{

alert("out of list");

return -1;

}

var nums =[];

var steps =[];

var j=1;

var i;

var tem=1;

var result = [];

for( i= bits; i>0; i--)

{

tem= tem *j;

j++;

if(index >= tem)

{

steps.push(tem);

nums.push(i);

}

else

{

break;

}

}

if(index > tem)

{

alert("out of list");

return -1;

}

for(var k= 1; k<=i;k++)

{

result.push(k);

}

for(var m= steps.length-1; m>=0; m--)

{

var times = parseInt(index/steps[m]);

index = index%steps[m];

if(index ==0)

{

if(times== 1)

{

for( var v=0; v< nums.length; v++)

{ result.push(nums[v]); }

}

else if(times >1)

{

for(var bb=nums.length -1; bb >=0; bb--)

{

if(times == 2)

{

var ttt = result[result.length-1];

result[result.length-1] = nums[bb];

nums[bb] = ttt;

break;

}

else

{

times--;

}

}

nums.sort(function(m, n){return m-n;}).reverse();

for( var vv=0; vv< nums.length; vv++)

{ result.push(nums[vv]); }

}

break;

}

else if(index >0)

{

if(times ==0)

{

result.push(nums[nums.length-1]);

nums.pop();

}

else if(times >0)

{

for(var b=nums.length -1; b >=0; b--)

{

if(times == 1)

{

var tt = result[result.length-1];

result[result.length-1] = nums[b];

nums[b] = tt;

break;

}

else

{

times--;

}

}

// result[result.length-1] += times;

// nums[nums.length -1 -times+1] -= times;

nums.sort(function(m, n){return m-n;}).reverse();

result.push(nums[nums.length-1]);

nums.pop();

}

}

}

return parseInt(result.join(""));

}