数据准备
- 在讲排列与组合之前,我们先定义数据元素类型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'
文章来源地址https://www.toymoban.com/news/detail-722416.html
文章来源:https://www.toymoban.com/news/detail-722416.html
到了这里,关于【算法教程】排列与组合的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!