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

sucanber 发布于 2015/03/18 22:15

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

0

n = 4; r = 20;

d1 = ceil(r/(n-1)!) = 4 故第1位是第4小的数“4”

n = n-1 = 3; r = r - (d1-1)(d1-1)! = 2;

d2 = ceil(r/(n-1)!) = 1 故第2位是剩余第1小的数“1”

n = n-1 = 2; r = r - (d2-1)(d2-1)! = 2;

d3 = ceil(r/(n-1)!) = 2 故第3位是剩余第2小的数“3”

0

0
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();
}

}

xie xie !
0

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)
{
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)
{
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(""));

}