排列組合
數(shù)學(xué)相關(guān)知識(shí)：5分鐘徹底了解排列組合
排列有序营勤，組合無序
3選2 ：排列個(gè)數(shù)：3*2 ；組合個(gè)數(shù)：3*2/2*1
選第一個(gè)元素時(shí)3種情況起惕；在除去了第一個(gè)元素后昨寞，在剩下的元素中繼續(xù)選出第二個(gè)元素玷或，2種情況熄求；
排列采取多分支遞歸的方式
? 單分支遞歸:
? 遞歸的結(jié)束情況時(shí)返回計(jì)算值蔑鹦，最后一層遞歸之前的遞歸方法返回值是下一次遞歸的返回值 return recur()
所以整個(gè)遞歸的返回值是遞歸結(jié)束時(shí)計(jì)算出的結(jié)果
function recur (inputVal) {
if (inputVal === 10) {
return inputVal
} else {
return recur(++inputVal)
}
}
console.log(recur(0)) // 10
? 多分支遞歸：
[1,2,3]與[A,B,C]兩兩組合夺克，先選數(shù)字再選字母
由于是多分支，所以需要數(shù)組儲(chǔ)存所有分支結(jié)果嚎朽。在遞歸的終止條件時(shí)得到一個(gè)分支的結(jié)果铺纽，此時(shí)將結(jié)果.push()儲(chǔ)存。每個(gè)分支都將結(jié)果儲(chǔ)存到同一個(gè)數(shù)組 result中哟忍，所以for循環(huán)結(jié)束后返回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' ]
排列：
每次從數(shù)組中選一個(gè)元素陷寝，可選情況為數(shù)組長度。將選了的數(shù)據(jù)從數(shù)組中剔除融撞，下次再選一個(gè)元素，可選情況為數(shù)組長度粗蔚。
function sequence (data, selectNum, lastVal, result) { // 排列
/*
data:Array;供選擇的數(shù)據(jù)
selectNum:num;選擇多少個(gè)數(shù)據(jù)
lastVal:string;初始值為‘’;初始值為''
result:Array;初始值為[];整個(gè)排序的結(jié)果
*/
if (selectNum === lastVal.length || !data.length) {
result.push(lastVal)
} else {
// 每次在剩下的data中選一個(gè)值
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' ]
組合：
從數(shù)組中[1,2,3]依次選取元素尝偎，每個(gè)元素都可選可不選，一共2^3中選項(xiàng)鹏控。其中選了2個(gè)元素的有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個(gè)也為遞歸終止條件当辐，當(dāng)data長度為0時(shí)也終止遞歸抖僵，但是要舍棄沒有選到兩個(gè)數(shù)的結(jié)果
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' ]
