排列组合
数学相关知识：5分钟彻底了解排列组合
排列有序，组合无序
3选2 ：排列个数：3*2 ；组合个数：3*2/2*1
选第一个元素时3种情况；在除去了第一个元素后，在剩下的元素中继续选出第二个元素，2种情况；
排列采取多分支递归的方式
单分支递归:
递归的结束情况时返回计算值，最后一层递归之前的递归方法返回值是下一次递归的返回值 return recur()
所以整个递归的返回值是递归结束时计算出的结果
function recur (inputVal) {
if (inputVal === 10) {
return inputVal
} else {
return recur(++inputVal)
}
}
console.log(recur(0)) // 10
多分支递归：
[1,2,3]与[A,B,C]两两组合，先选数字再选字母
由于是多分支，所以需要数组储存所有分支结果。在递归的终止条件时得到一个分支的结果，此时将结果.push()储存。每个分支都将结果储存到同一个数组 result中，所以for循环结束后返回result得到所有分支值。
function branchRecur (step, lastVal, result = []) {
if (step === 0) {
result.push(lastVal)
} else {
let data = [['A', 'B', 'C'],[1,2,3]]
for (let i = 0; i < data.length; i++) {
branchRecur(step - 1, lastVal + data[step - 1][i], result)
}
return result
}
}
console.log(branchRecur(2,'')) //[ '1A', '1B', '2A', '2B' ]
排列：
每次从数组中选一个元素，可选情况为数组长度。将选了的数据从数组中剔除，下次再选一个元素，可选情况为数组长度。
function sequence (data, selectNum, lastVal, result) { // 排列
/*
data:Array;供选择的数据
selectNum:num;选择多少个数据
lastVal:string;初始值为‘’;初始值为''
result:Array;初始值为[];整个排序的结果
*/
if (selectNum === lastVal.length || !data.length) {
result.push(lastVal)
} else {
// 每次在剩下的data中选一个值
for (let i = 0; i < data.length; i++) {
let newData = [].concat(data)
newData.splice(i, 1)
sequence(newData, selectNum, lastVal + data[i], result)
}
return result
}
}
console.log(sequence([1, 2, 3], 2, '', [])) //[ '12', '13', '21', '23', '31', '32' ]
组合：
从数组中[1,2,3]依次选取元素，每个元素都可选可不选，一共2^3中选项。其中选了2个元素的有3种
function combine (data, lastVal, result = []) {
if (!data.length) {
result.push(lastVal)
return
}
let newData = [].concat(data)
let item = newData.shift()
combine(newData, lastVal + item, result) // 选
combine(newData, lastVal, result) // 不选
return result
}
console.log(combine([1, 2, 3], '')) //[ '123', '12', '13', '1', '23', '2', '3', '' ]
所以加以限制条件，3选2，选到2个也为递归终止条件，当data长度为0时也终止递归，但是要舍弃没有选到两个数的结果
function combine (data, selectNum, lastVal, result = []) {
if (lastVal.length === selectNum || !data.length) {
lastVal.length === selectNum && result.push(lastVal)
return
}
let newData = [].concat(data)
let item = newData.shift()
combine(newData, selectNum, lastVal + item, result) // 选
combine(newData, selectNum, lastVal, result) // 不选
return result
}
console.log(combine([1, 2, 3], 2, '')) // [ '12', '13', '23' ]
