【算法教程】排列与组合的实现

数据准备 在讲排列与组合之前，我们先定义数据元素类型Fruit class Fruit{ constructor(name,price){ this.name = name this.price = price } } 排列 对N个不同元素进行排序，总共有多少不同的排列方式？ Step1: 从N个元素中取1个，共N种取法 Step2: 从剩下N-1个元素取1个，共N-1种 ...... StepN: 从剩1个元素中取1个，共1种 所以共有　A=N*(N-1)....*1 =N! 例子:某水果店有以下水果，请对所有水果进行全排列，请输出所有排列 let fruits = [ new Fruit('apple',5.3), new Fruit('banana',3.2), new Fruit('orange',4.6), new Fruit('watermelon',2.5) ] 排列算法的javascript实现模板(DSF,最优解in-place) const premutation = (elements)=>{ let res = [] const swap = (arr,i1,i2)=> [arr[i1],arr[i2]] = [arr[i2],arr[i1]] const dsf = (elements,k = 0)=>{ let len = elements.length if(k == len-1){ // 如果想从N=4中，取3个的全排 只需要改这个k=3 res.push([...elements.slice(0,k+1)]) return } for(let i = k; i < len - 1 ; i++){ swap(elements, i, k) // 从剩下[k,...,(len-2)]中 取一个 放到当前k位置 dsf(elements, k + 1) // dsf继续下一个位置 [k+1,...,(len-2)] swap(elements,i , k) // 为下一个迭代(k+1)做回滚 } } dsf(elements) return res } let premutations = premutation(fruits) premutations.forEach((e,i)=>console.log(i,...e.map(x=>x.name))) 测试结果 0 'apple' 'banana' 'orange' 'watermelon' 1 'apple' 'orange' 'banana' 'watermelon' 2 'banana' 'apple' 'orange' 'watermelon' 3 'banana' 'orange' 'apple' 'watermelon' 4 'orange' 'banana' 'apple' 'watermelon' 5 'orange' 'apple' 'banana' 'watermelon' 组合 对N个不同元素进行排序，总共有多少不同的组合方式？ N个元素中，每个元素要么被放到某个组合中，或者不放,2种选择 所以共有 C=2^N 算法实现： 同样我们可以用DSF，但是还有更优解法-- 整型编码/bitmap 2^N种情况可以用N个bit来表示，通过实现对数组索引index来编码 同样的例子:请输出所有组合 let fruits = [ new Fruit('apple',5.3), new Fruit('banana',3.2), new Fruit('orange',4.6), new Fruit('watermelon',2.5) ] 组合算法的javascript实现模板(bitmap) const combination = (elements)=>{ let res = [] let len = elements.length let counts = 1 << len for(let bitmap = 0 ; bitmap < counts; bitmap++){ let set = [] for(let i=0 ; i < len ; i++){ if((1<<i)&bitmap){ //对应位为1，怎加入当前集合种 set.push(i) } } // set 只是数组索引的组合，需要转成对应element res.push(set.map(i=>elements[i])) // 完成一个集合的收集 } return res } let combinations = combination(fruits) combinations.forEach((e,i)=>console.log(i,...e.map(x=>x.name))) 测试结果 0 '' 1 'apple' 2 'banana' 3 'apple' 'banana' 4 'orange' 5 'apple' 'orange' 6 'banana' 'orange' 7 'apple' 'banana' 'orange' 8 'watermelon' 9 'apple' 'watermelon' 10 'banana' 'watermelon' 11 'apple' 'banana' 'watermelon' 12 'orange' 'watermelon' 13 'apple' 'orange' 'watermelon' 14 'banana' 'orange' 'watermelon' 15 'apple' 'banana' 'orange' 'watermelon'