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

这篇具有很好参考价值的文章主要介绍了【算法教程】排列与组合的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据准备

  • 在讲排列与组合之前,我们先定义数据元素类型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

到了这里,关于【算法教程】排列与组合的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】 排列与组合算法详解(进阶篇)

    写在前面 我上次发了一篇题解:C++排列与组合算法详解 最开始,我是抱着水题解的想法写的,但却成为了阅读量 最高 的文章,没有之一。 所以今天咱们来重制一篇文章,介绍几个进阶优化版的算法。 算法1:朴素算法 思路 具体见 C++排列与组合算法详解 缺点 不能将结果取

    2024年02月13日
    浏览(39)
  • 【算法】递归、回溯、剪枝、dfs 算法题练习(组合、排列、总和问题;C++)

    后面的练习是接着下面链接中的文章所继续的,在对后面的题练习之前,可以先将下面的的文章进行了解👇: 【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题(C++) 思路 题意分析 :要求根据给出的数字,算出合法的括号组成个数。根据题目,我们可以总

    2024年02月22日
    浏览(48)
  • 【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合

    📖题目描述 题目出处 :电话号码的字母组合 示例: 📖题解  这是一道典型的排列组合问题,根据输入,我们需要找到所有的组合。下面以输入字符串 digits = \\\"23\\\" 为例来讲解这道题目。 图解: 分析:  首先要知道输入的字符串 \\\"23\\\" 中的数字字符分别对应哪些字符串,其中

    2024年02月16日
    浏览(39)
  • (3)回溯算法团灭子集、组合、排列问题 -- 元素无重可复选

    回溯算法团灭子集、组合、排列问题 根据元素是否重复和是否可复选,分为以下三种变体: 1、元素无重不可复选 2、元素有重不可复选 3、元素无重可复选 该篇给出第三种情况的代码,另外两种的实现见上方变体链接。

    2024年02月09日
    浏览(30)
  • 递归实现 组合问题+排列问题(DFS)

    目录 递归实现排列型枚举 递归实现排列类型枚举 II  递归实现组合型枚举 递归实现组合型枚举 II 递归实现指数型枚举 递归实现指数型枚举 II 递归不是循环,递归利用了系统栈,只要是函数都会被系统管理。当执行到函数地址入口时就会为函数在系统栈上分配一块内存。当

    2024年02月15日
    浏览(44)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(42)
  • PostgreSQL里实现计算多个数字的排列组合

    在进行排列组合的时候,每一次需要知道是否有重复的值,并过滤出已经排列过的值。这个可以创建支持可变参数的函数来实现。下边的函数用到了聚合判断,并且可变参数使用variadic标记的数组。 然后是如何使用这个函数结合查询语句对一组数据进行排列组合。 先创建一个

    2024年02月21日
    浏览(32)
  • python排列组合

    itertools.permutations(iterable,r=None) 功能:连续返回由iterable序列中的元素生成的长度为r的排列 如果r未指定或为None,r默认设置为iterable的长度,即生成包含所有元素的全排列 简单应用示例如下: 代码清单1-1: 输出: ab ac ba bc ca cb 问:permutations()按什么顺序输出序列? 答:按元

    2024年02月06日
    浏览(37)
  • 数学-排列组合的理解

    排列是有顺序的排队,从 m 中选择 n 个进行排队,第 1 个有 m-0 种选择,第 2 个有 m-1 种选择,自然的,第 n 个有 m-(n-1) 种选择。因为有顺序,可以看出前面的选择,会后面影响后面的选择,所以将选择每个的可能数相乘。 A m n = ( m − 0 ) ∗ ( m − 1 ) ∗ . . . ∗ ( m − ( n − 1

    2023年04月16日
    浏览(41)
  • python中的排列和组合

    itertools.permutations(iterable,r=None) 功能:连续返回由iterable序列中的元素生成的长度为r的排列 如果r未指定或为None,r默认设置未iterable的长度,即生成包含所有元素的全排列        permutations()是按元素的位置顺序输出的元素的排列,也就是说,输出的排列的顺序是位置的字典序

    2024年02月09日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包