算法讨论:已知一个排列在其按字典顺序的全排列中的序号,求该排列
好吧,承认标题有点绕,文字不太好描述,还是举例吧,
比如我们知道字符串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(""));
}
热文精选
更多资讯推荐
更多- Stable Diffusion 2.0 发布,加强成人内容过滤
- .NET 7 正式发布
- A3Mall 开源商城系统 v2.1 发布
- FydeOS v14 版本更新:优化输入法体验+重构安卓子系统+全新应用启动器
- ThinkPHP V6.0.8版本发布——多环境变量配置支持
- 毕昇 JDK 8u292、11.0.11 发布!
- KubeVela 1.0:开启可编程式应用平台的未来
- Eclipse 4.19 稳定版发布
- 阿里巴巴 Arthas 3.5.0 版本发布,支持反编译打印行号和统一鉴权
- Debian 11 Bullseye 即将进入冻结,Debian 13 代号 Trixie
- Rancher 2.5 发布,新增支持边缘集群的 GitOps
- FlashDB IoT 超轻量级嵌入式数据库