4
回答
算法讨论:已知一个排列在其按字典顺序的全排列中的序号,求该排列
终于搞明白,存储TCO原来是这样算的>>>   

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

比如我们知道字符串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

求指教,最好能用代码/伪代码阐述。。。



举报
sucanber
发帖于3年前 4回/983阅
共有4个答案 最后回答: 3年前

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”

以此类推,仅供参考。

--- 共有 4 条评论 ---
sucanber回复 @方棱 : 嗯 思路很清晰, 离正确很近了,晚点下班回去再琢磨琢磨 3年前 回复
方棱回复 @sucanber : 嗯嗯,细节我也没有多想,你领会 d=ceil(r/(n-1)!) 的思想就行。 3年前 回复
sucanber接下来: n= n -1 =1, r=r- (d3-1)(d3-1)! = 1, d4=ceil(r/(n-1)!) = 1 这个第“1”小的数上面已经有了, 那就解释不通了呀? 3年前 回复
sucanber厉害! 3年前 回复

对于非固定字符串,我想请教下这个算法的工程意义。哈。确实不懂,楼上给出的方法时确定字符串的处理。至于已知编码规则,根据存储顺序位获取编码内容,这是索引问题,不是你说的问题,当编码构建时,其存储位置记录下来,形成索引,直接查就行了。再差,用hash即可。

存储顺序和编码规则是无关的。依据编码规则计算存储顺序,至少工程上是扯淡的行为。哈。

--- 共有 1 条评论 ---
sucanber 谢谢 赞! 3年前 回复
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();
    }

}



--- 共有 1 条评论 ---
sucanberxie xie ! 3年前 回复

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

}

--- 共有 1 条评论 ---
sucanber不错哦, 也是逐位试探取值,求余递进的方法。 不过我现在不需要这个算法了,就像2楼说的,我只要先把固定串的序列和索引关系遍历一次存入DB或文件,下次需要直接查询就可以了。 thank you ! 3年前 回复
顶部