javascript算法题 求任意一个1-9位不重复的N位数在该组合中的大小排列序号

具体题目是这样的：

　　从1--9中选取N个数字，组成不重复的N位数，从小到大进行编号，当输入其中任何一个数M时，能找出该数字对应

的编号。如 N=3，M=213. 输出：[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]--->X=2

　　首先看到题目想到的是生成一个从少到大的全排列的数组，然后再遍历数组得到对应的序号(数组下标加1)，又或者想到一个个从小到大的生成push进数组，然后判断该数是不是当前题目给的数，如果是的话要求的序号就是当前数组的长度，比前面好的一点的是不用浪费时间去计算生成后面的项。生成本身复杂度不高，如果扩展到16进制甚至36进制且给一个很大的数的话就不好了，还有需要浪费一部分空间去保存用不上的数据。或许我们可以尝试其它不用生成的方法。

　　我们先理想化下题目，如果给了一个数N，那么，M就由1-N N位数组成（比如N=4,那M就由1234几个数字组合，而不是其它1349等其它组合）。之所以这么做是因为我们要简化条件好分析出共性得到解题的方法，而且要从随机的情况转化成理想的情况也不难，本文就不啰嗦了。先分析下题目给的例子，[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)] 213在第三位，首数字是2，也就是说首数字是1的都在他前面(123,132)，再来看第二个数字和后面的数的组合13，首字母1已经是最小的了，他前面不可能有任何数，而第三个数字3就不用看了，因为如果前面的位数都确定了，最后一位就只有一种可能了，得出来的结果就是213的前面有2(首位)+0(二位)+0(尾位)=2个数，也就是说当前数在第3位，对比一下答案确实是这样的，其它数的分析也一样。由此可以得出我们要一个函数(也就是下面代码的setAll())可以算出某一位比当前数小的可能性总数，然后累加起来+1就是想要的结果，请看代码实现：

代码如下:

//函数功能:得到每一位，如果是其它数的话比当前小的可能性总数
//a 当前数序号（从小到大）
//n 当前数总数
function getAll(a,n){
var sum=1; //总数
for(var i=n;i>1;i--)sum=sum*i; //算出n个有序的位置放n个不同的数字的可能性总数
return sum*(a-1)/n; //算出比首位为a的比当前数小的数的可能性总数
}

//m 要计算的数序列
//a 存放当前位的数在和它后位的数而组成的数它的大小序号
// 比如 213 的 a数组为 [2,1,1]; a[0]为2是因为 213 首位2在213三个数字中排第2小;而a[1]为1是因为13的首位1在13中排第一小
function find(m){
m=(m+"").split(""); //把当前数拆分放在数组里面好方便对每一位进行计算
var a=new Array(m.length+1).join(1).split(""); //快速生成长度为m的长度的值都为1的数组，a数组的功能说明看上面函数头的注释
for(var i=0;i<m.length-1;i++){
for(var j=i+1;j<m.length;j++){
if(+m[i]>+m[j])a[i]++;
}
} //生成a数组
console.log("a数组：",a);
for(i=1,sum=1;i<m.length;i++){
sum+=getAll(+a[i-1],m.length-i+1); //循环调用getAll计算每一位与其后面的数成的组合比当前组合小的可能性总数
}
return m+" 排在全排列的第"+sum+"位";
}
console.log(find(213)); //输出3
console.log(find(123)); //输出1
console.log(find(231)); //输出4
console.log(find(312)); //输出5
console.log(find(4321)); //输出24
console.log(find(21)); //输出2
console.log(find(1)); //输出1

赞 (0)

相关推荐

  • JavaScript全排列的六种算法 具体实现

    全排列是一种时间复杂度为:O(n!)的算法,前两天给学生讲课,无意间想到这个问题,回来总结了一下,可以由7种算法求解,其中动态循环类似回溯算法,实现起来比较繁琐,故总结了6种,以飨读者.所有算法均使用JavaScript编写,可直接运行.算法一:交换(递归) 复制代码 代码如下: <html xmlns="http://www.w3.org/1999/xhtml">  <head>      <meta http-equiv="Content-T

  • js实现字符全排列算法的简单方法

    实例如下: <!doctype html> <html lang="en"> <head> <meta charset="UTF-8"> <title>字符全排列</title> </head> <body> <script> function charsMap(o){ o = (o+"").replace(/(\w)(?=\w*\1)/g

  • javascript使用递归算法求两个数字组合功能示例

    本文实例讲述了javascript使用递归算法求两个数字组合功能.分享给大家供大家参考,具体如下: // 12 ,3,4 两个数字组合 最后结果 应该是 // 13 // 14 // 23 // 24 // 34 // 这5种 用程序 怎么算出来 // 是求组合的算法 // var arr = [12, 3, 4]; // var len = arr.length; // var result = []; // for (var i = 0; i < len; i++) { // for (va

  • 几种经典排序算法的JS实现方法

    一.冒泡排序 function BubbleSort(array) { var length = array.length; for (var i = length - 1; i > 0; i--) { //用于缩小范围 for (var j = 0; j < i; j++) { //在范围内进行冒泡,在此范围内最大的一个将冒到最后面 if (array[j] > array[j+1]) { var temp = array[j]; array[j] = array[j+1]; arra

  • JS实现的全排列组合算法示例

    JS实现的全排列组合算法示例

    本文实例讲述了JS实现的全排列组合算法.分享给大家供大家参考,具体如下: 全排列组合算法,例如a,b,c,d进行全排列组合,则组合结果为:a,b,ab,c,ac,bc,abc,d,ad,bd,abd,cd,acd,bcd,abcd.实现思路:从数据源拿出一个元素,依次与已存在的组合数据进行组合,循环上面操作直到数据源没有数据为止. 例子: 数据源a,b,c 1.拿出a,组合数据group为空,插入数据源a元素到组合数据group,此时group=[a] 2.拿出b,组合数据group拿出a,a和

  • js算法中的排序、数组去重详细概述

    其实在js中实现数组排序,采用数组中sort方法实现还是比较简单的: 一.排序 简单实现数组排序 复制代码 代码如下: var arr = [];  for(var i=0;i<20;i++){      arr.push(Math.floor(Math.random()*100))  }  arr.sort(function(a,b){      return a>b?1:-1;  })  alert(arr) 不能简单使用sort方法,默认情况下 sort方法是按ascii字母顺序排序的,

  • JS实现的数组全排列输出算法

    本文实例讲述了JS实现的数组全排列输出算法.分享给大家供大家参考.具体分析如下: 这段js代码对数组进行全排列输出,改进了一些老的代码 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. function permute(input) { var permArr = [], usedChars = []; function main(input){ var i, ch; for (i = 0; i < i

  • JavaScript实现SHA-1加密算法的方法

    本文实例讲述了JavaScript实现SHA-1加密算法的方法.分享给大家供大家参考.具体实现方法如下: 调用方法:hex_sha1即可. 复制代码 代码如下: /*  *  * A JavaScript implementation of the Secure Hash Algorithm, SHA-1, as defined  * in FIPS PUB 180-1  *  * By lizq  *  * 2006-11-11  *  */ /*  *  * Configurable var

  • js-FCC算法-No repeats please字符串的全排列(详解)

    把一个字符串中的字符重新排列生成新的字符串,返回新生成的字符串里没有连续重复字符的字符串个数.连续重复只以单个字符为准 例如, aab 应该返回 2 因为它总共有6中排列 (aab, aab, aba, aba, baa, baa),但是只有两个 (aba and aba)没有连续重复的字符 (在本例中是 a). 从网上资料获得了一些思路,我的代码: function permAlone(str) { var arr=str.split(""); var perarr=[]; var

  • javascript常用经典算法实例详解

    javascript常用经典算法实例详解

    本文实例讲述了javascript常用算法.分享给大家供大家参考,具体如下: 入门级算法-线性查找-时间复杂度O(n)--相当于算法界中的HelloWorld //线性搜索(入门HelloWorld) //A为数组,x为要搜索的值 function linearSearch(A, x) { for (var i = 0; i < A.length; i++) { if (A[i] == x) { return i; } } return -1; } 二分查找(又称折半查找) - 适用于已排好序的

  • Javascript中的常见排序算法

    具体代码及比较如下所示: 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">  <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">

  • js数组去重的5种算法实现

    1.遍历数组法 最简单的去重方法,实现思路:新建一新数组,遍历传入数组,值不在新数组就加入该新数组中:注意点:判断值是否在数组的方法"indexOf"是ECMAScript5 方法,IE8以下不支持,需多写一些兼容低版本浏览器代码,源码如下: // 最简单数组去重法 function unique1(array){ var n = []; //一个新的临时数组 //遍历当前数组 for(var i = 0; i < array.length; i++){ //如果当前数组的第i已

随机推荐