如何看懂这段关于js排列组合代码?

topBing
  • 47

代码:

/**
  * 排列组合算法
  **/
bonusCombination (arr, num, fun) {
  if (arr.length < num || num > 10) {
    return []
  }
  let variable = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u']
  let replaceStr = '#$#'
  let str = 'var arr=arguments[0]; var fun=arguments[1];  var ret=[]; for (var a = 0; a < arr.length; a++) { ' + replaceStr + ' } return ret;'
  for (let i = 1; i < num; i++) {
    str = str.replace(replaceStr, ' for (var ' + variable[i] + ' =' + variable[i - 1] + '+ 1; ' + variable[i] + ' < arr.length; ' + variable[i] + '++) { ' + replaceStr + '  }')
  }
  let temp = 'var temp= [];'
  for (let i = 0; i < num; i++) {
    temp += 'temp.push(arr[' + variable[i] + ']);'
  }
  if (fun) {
    temp += 'ret.push(fun(temp)); '
  } else {
    temp += 'ret.push(temp);'
  }
  str = str.replace(replaceStr, temp)
  return (new Function(str)).apply(null, [arr, fun])
}

图示:
运行结果

  1. 看不懂为什么用字符串做变量,这个方法还有其他的功能吗?
  2. 一开始为什么定义一个 variable;
  3. 请一步一步来解释。
回复
阅读 2.1k
5 个回答

一行一行解释源码,估计也不太好理解;我们从另外一个角度来看这个问题。

返回的是动态函数

首先看 bonusCombination 函数的返回语句是:return (new Function(str)).apply(null, [arr, fun])。这条语句的分解如下::

  • new Function(str) :含义是利用 str 字符串动态构造出函数,我们暂且称这个构造出来的函数名为 strFn (即 var strFn = new Function(str)
  • 这样就有 strFn.apply(null, [arr, fun]),转换成我们平时可以理解的形式就是 strFn(arr, fun)

从这里我们可以看出,这个 bonusCombination 的目的是动态构建一个函数 strFn,该函数接受两个入参 arrfun —— 而这两个入参就是我们传给 bonusCombination 的入参;

对应你给的例子,这里的 arr 就是 [1,2,3,4],而 funnull

入参 num 的作用,动态创建函数体

我们知道 bonusCombination 还有一个入参,就是 num,它的作用就是 锻造 上述动态函数 strFn 的具体内容,利用这个 num 入参来影响那一大段字符操作,这样也就影响了动态函数的具体内容:

函数体内容

对于阅读这样的函数,要理解它的含义,最好的办法就是枚举。

比如我们让 num2:那么动态构建的函数 strFn 结构体如下:

var strFn2 = function(arr, fun){
  var arr=arguments[0]; 
  var fun=arguments[1];  
  var ret=[]; 
  for (var a = 0; a < arr.length; a++) {
    for(var b = a + 1; b < arr.length; b++){
        var temp = [];
          temp.push(arr[a]); 
          temp.push(arr[b]); 
          if(fun){
            ret.push(fun(temp));
        } else {
            ret.push(temp); 
        }
    } 
  };
  return ret;
}

可见函数体内包含 2 次循环(因为 num 值为 2),返回的 ret 就是结果值;

也就说调用 bonusCombination([1,2,3,4],2) 就相当于调用 strFn2([1,2,3,4]),返回值就是你题中的 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

同样如果我们让 num3:那么动态构建的函数 strFn 结构体如下:

var strFn3 = function(arr, fun){
  var arr=arguments[0]; 
  var fun=arguments[1];  
  var ret=[]; 
  for (var a = 0; a < arr.length; a++) {
    for(var b = a + 1; b < arr.length; b++){
      for(var c = b + 1; c < arr.length; c++) {
        var temp = [];
          temp.push(arr[a]); 
          temp.push(arr[b]); 
          temp.push(arr[c]);
          if(fun){
            ret.push(fun(temp));
        } else {
            ret.push(temp); 
        }
      }
    } 
  };
  return ret;
}

函数体内包含 3 次循环(因为 num 值为 3);此时调用 bonusCombination([1,2,3,4],3) 就相当于调用 strFn3([1,2,3,4]),返回值是 [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

你也可以自己试一下让 num4 或者 1,写出的函数体内容是怎么样的,你就能彻底明白这个 bonusCombination 函数的作用了。

回答你的问题

问题1:看不懂为什么用字符串做变量,这个方法还有其他的功能吗?
回答:字符串做变量就是为了动态构造函数体内容,依据 num 的不同值动态生成不同的 strFn 函数 —— 从这个角度上来讲 bonusCombination 就是一个 工厂函数

该方法还有另外的功能,体现在入参 fun 上,可以对每个结果元素调用 fun(temp),相当于使用数组的 map 功能。

问题2:一开始为什么定义一个 variable;
回答:主要是为动态函数体提供足够多的中间变量,没啥具体含义,只要是符合 js 变量名称就可以。这里使用 ab... 这些变量名,估计是为了简单起见,你可以用任何符合 js 变量名称规范的字符串就行。

问题3:请一步一步来解释
回答:读懂上面两小节的分析或者参考前一个回答,每一行解释这里就不附上了。

其他

这种利用 Function 动态函数构造出来的功能函数,性能堪忧;
你也知道,如果 arr 入参数组越长,num 越大,那么嵌套的循环体也就越多,性能就越差

这样的代码虽然能运行,但质量比较糟糕,还有很大的性能隐患,不能放在线上正式的产品中使用。这段代码比较适合用来学习 Function 的功能,以及 组合数学 的相关知识。

这种方式的编程属于 元编程 范畴,可以参考我最近写的文章 《【资源集合】 ES6 元编程(Proxy & Reflect & Symbol)》了解更多。后续有机会,我看能否使用 Proxy & Reflect 来重写这个 bonusCombination 函数。

/**
  * 排列组合算法
  **/
bonusCombination(arr, num, fun) {
  if (arr.length < num || num > 10) {
    return []
  }
  // 一堆随机的变量名称
  let variable = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u']
  // 替代内容的字面量 token
  let replaceStr = '#$#'
  // 函数体的基本模板
  let str = 'var arr=arguments[0]; var fun=arguments[1];  var ret=[]; for (var a = 0; a < arr.length; a++) { ' + replaceStr + ' } return ret;'
  // 替换 replaceStr 为【排列组合】多重嵌套循环
  for (let i = 1; i < num; i++) {
    str = str.replace(replaceStr, ' for (var ' + variable[i] + ' =' + variable[i - 1] + '+ 1; ' + variable[i] + ' < arr.length; ' + variable[i] + '++) { ' + replaceStr + '  }')
  }
  // 替换 replaceStr 为【记录排列组合结果】的代码
  let temp = 'var temp= [];'
  for (let i = 0; i < num; i++) {
    temp += 'temp.push(arr[' + variable[i] + ']);'
  }
  if (fun) {
    temp += 'ret.push(fun(temp)); '
  } else {
    temp += 'ret.push(temp);'
  }
  str = str.replace(replaceStr, temp)
  // 使用 Function 将 str 转化为一个函数并运行
  return (new Function(str)).apply(null, [arr, fun])
}

// Done ...

并没有什么难理解的,你唯一需要理解的是,Function 这个构造函数的作用。

你这个问题,就好比20年前一个很流行的节目:正大综艺。主持人跑到欧洲某个地方,进入一户人家,突然指着墙上一个物件问大家:这是什么?干嘛用?怎么用?

我怎么知道?

你应该至少带上以下信息:

  1. 这个函数你从哪里找到的?
  2. 你学习这个函数希望实现什么效果?
  3. 你做过哪些尝试,收获哪些成果,遇到哪些问题?

个人感觉 还不如递归来的快


你运行下这个看看 很有意思

/**
  * 排列组合算法
  **/
function bonusCombination (arr,num,fun){
  if (arr.length < num || num > 10) {
    return []
  }

  function step (arr_in,num_in) {
    if (num_in==1){
      let res = arr_in.map((v)=>{
        let temp = fun?fun(v):v
        return [temp]
      })
      return res
    }
    let ret=[]
    for (let i=1;i<arr_in.length;){
      let temp = fun?fun(arr_in[0]):arr_in[0]
      let currVal = [temp]
      arr_in = arr_in.slice(i)
      step(arr_in,num_in-1) .forEach((arr2)=>{
        ret.push(currVal.concat(arr2))
      })
    }
    return ret;
  }
  return  step(arr,num);
}


/**
  * 排列组合算法
  **/
 function bonusCombination2 (arr, num, fun) {
  if (arr.length < num || num > 10) {
    return []
  }
  let variable = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u']
  let replaceStr = '#$#'
  let str = 'var arr=arguments[0]; var fun=arguments[1];  var ret=[]; for (var a = 0; a < arr.length; a++) { ' + replaceStr + ' } return ret;'
  for (let i = 1; i < num; i++) {
    str = str.replace(replaceStr, ' for (var ' + variable[i] + ' =' + variable[i - 1] + '+ 1; ' + variable[i] + ' < arr.length; ' + variable[i] + '++) { ' + replaceStr + '  }')
  }
  let temp = 'var temp= [];'
  for (let i = 0; i < num; i++) {
    temp += 'temp.push(arr[' + variable[i] + ']);'
  }
  if (fun) {
    temp += 'ret.push(fun(temp)); '
  } else {
    temp += 'ret.push(temp);'
  }
  str = str.replace(replaceStr, temp)
  return (new Function(str)).apply(null, [arr, fun])
}

let arr = [
  'a',
  'b',
  'c',
  'd',
  'e',
  'f',
  'g',
  'h',
  'i',
  'j',
  'k',
  'l',
  'm',
  'n',
  'o',
  'p',
  'q',
  'r',
  's',
  't',
  'u',
  'v',
  'w',
  'x',
  'y',
  'z'
]



console.time('bonusCombination')
let result = bonusCombination([...arr],10,(val)=>{return val});
console.log(result)
console.timeEnd('bonusCombination')

console.time('bonusCombination2')
let result2 = bonusCombination([...arr],10,(val)=>{return val});
console.log(result2)
console.timeEnd('bonusCombination2')

跑起来这么卡?

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏