网站建设项目公司,网站建设和网站开发,房地产行业网站建设报价方案,seo0577数据准备
在讲排列与组合之前#xff0c;我们先定义数据元素类型Fruit
class Fruit{constructor(name,price){this.name namethis.price price}
}排列
对N个不同元素进行排序#xff0c;总共有多少不同的排列方式#xff1f;
Step1: 从N个元素中取1个#xff0c;共N种…数据准备
在讲排列与组合之前我们先定义数据元素类型Fruit
class Fruit{constructor(name,price){this.name namethis.price price}
}排列
对N个不同元素进行排序总共有多少不同的排列方式
Step1: 从N个元素中取1个共N种取法
Step2: 从剩下N-1个元素取1个共N-1种
......
StepN: 从剩1个元素中取1个共1种
所以共有 AN*(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.lengthif(k len-1){ // 如果想从N4中取3个的全排 只需要改这个k3res.push([...elements.slice(0,k1)])return}for(let i k; i len - 1 ; i){swap(elements, i, k) // 从剩下[k,...,(len-2)]中 取一个 放到当前k位置dsf(elements, k 1) // dsf继续下一个位置 [k1,...,(len-2)]swap(elements,i , k) // 为下一个迭代(k1)做回滚}}dsf(elements)return res
}
let premutations premutation(fruits)
premutations.forEach((e,i)console.log(i,...e.map(xx.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种选择
所以共有 C2^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.lengthlet counts 1 lenfor(let bitmap 0 ; bitmap counts; bitmap){let set []for(let i0 ; i len ; i){if((1i)bitmap){ //对应位为1怎加入当前集合种set.push(i)}}// set 只是数组索引的组合需要转成对应elementres.push(set.map(ielements[i])) // 完成一个集合的收集}return res
}
let combinations combination(fruits)
combinations.forEach((e,i)console.log(i,...e.map(xx.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
