当前位置: 首页 > news >正文

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

数据准备

  • 在讲排列与组合之前,我们先定义数据元素类型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种
所以共有 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.lengthif(k == len-1){ // 如果想从N=4中,取3个的全排 只需要改这个k=3res.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.lengthlet counts = 1 << lenfor(let bitmap = 0 ; bitmap < counts; bitmap++){let set = []for(let i=0 ; i < len ; i++){if((1<<i)&bitmap){ //对应位为1,怎加入当前集合种set.push(i)}}// set 只是数组索引的组合,需要转成对应elementres.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'

相关文章:

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

数据准备 在讲排列与组合之前&#xff0c;我们先定义数据元素类型Fruit class Fruit{constructor(name,price){this.name namethis.price price} }排列 对N个不同元素进行排序&#xff0c;总共有多少不同的排列方式&#xff1f; Step1: 从N个元素中取1个&#xff0c;共N种…...

uniapp实现简单的九宫格抽奖(附源码)

效果展示 uniapp实现大转盘抽奖 实现步骤&#xff1a; 1.该页面可设置8个奖品&#xff0c;每个奖品可设置中奖机会的权重&#xff0c;如下chance越大&#xff0c;中奖概率越高&#xff08;大于0&#xff09; // 示例代码 prizeList: [{id: 1,image: "https://img.alicdn…...

C++设计模式_09_Abstract Factory 抽象工厂

与上篇介绍的Factory Method工厂方法模式一样&#xff0c;Abstract Factory 抽象工厂模式也属于典型的“对象创建模式”模式&#xff0c;解决的问题也极其相似&#xff0c;在理解了Factory Method工厂方法模式的基础上再去理解Abstract Factory 抽象工厂模式就会变得更加容易。…...

一些前端面试思考

回流和重绘 先牢记这句话&#xff0c;回流必将引起重绘&#xff0c;而重绘不一定会引起回流。回流的代价要远大于重绘。 当你给一个元素更换颜色&#xff0c;这样的行为是不会影响页面布局的&#xff0c;DOM树不会变化&#xff0c;但颜色变了&#xff0c;渲染树得重新渲染页面&…...

Spring MVC(上)

1、Spring MVC简介&#xff1a; MVC是一种软件架构的思想&#xff0c;将软件按照模型、视图、控制器来划分 M&#xff1a;Model&#xff0c;模型层&#xff0c;指工程中的JavaBean&#xff0c;作用是处理数据 JavaBean分为两类&#xff1a; 一类称为实体类Bean&#xff1a;专…...

ORACLE内存结构

内存体系结构 ​​​​​​​ 目录 内存体系结构 2.1自动内存管理 2.2自动SGA内存管理 2.3手动SGA内存管理 2.3.1数据库缓冲区 2.3.1.1保留池 2.3.1.2回收池 2.3.2共享池 2.3.2.1SQL查询结果和函数查询结果 2.3.2.2库缓存 2.3.2.3数据字典缓存 2.3.3大池 2.3.4 …...

excel常用的几个函数

1、MID函数 通常用来返回返回指定字符串中的子串。 函数公式&#xff1a; MID(string, starting_at, extract_length) String&#xff08;必填&#xff09;&#xff1a;包含要提取字符的文本字符串 starting_at&#xff08;必填&#xff09;&#xff1a;文本中要提取的第一个字…...

【Bug】【内存相关】偶然发现一个内存溢出Bug复盘

一、问题 跑自动化用例的时候&#xff0c;uat-sg环境&#xff0c;发现SGW经常会返回 502 Bad Gateway响应 二、原因 经过SRE和BE Dev共同排查&#xff0c;502 是从ALB-- > 后端服务 后端服务无法响应导致&#xff0c;ALB会直接给客户端返回502。 服务端&#xff1a;由于c…...

python读写.pptx文件

1、读取PPT import pptx pptpptx.Presentation(rC:\Users\user\Documents\\2.pptx) # ppt.save(rC:\Users\user\Documents\\1.pptx) # slideppt.slides.add_slide(ppt.slide_layouts[1])# 读取所有幻灯片上的文字 for slide in ppt.slides:for shape in slide.shapes:if shape…...

【Godot】【BUG】4.x NavigationAgent 导航不生效

4.2.beta2 试了半天才发现原来默认只对第一个有导航的 TileMap 的第 1 层 生效&#xff0c;而我设置的导航层不是第一层&#xff0c;然后我新建了一个 TileMap 将导航的瓦片设置到这个 TileMap 上了&#xff0c;如图 这样就解决了问题&#xff0c;不用再修改默认设置的东西了&a…...

Rust逆向学习 (1)

文章目录 Hello, Rust Reverse0x01. main函数定位0x02. main函数分析line 1line 2line 3line 4~9 0x03. IDA反汇编0x04. 总结 近年来&#xff0c;Rust语言的热度越来越高&#xff0c;很多人都对Rust优雅的代码和优秀的安全性赞不绝口。对于开发是如此&#xff0c;对于CTF也是如…...

【Golang | reflect】利用反射实现方法的调用

引言 go语言中&#xff0c;如果某个数据类型实现了一系列的方法&#xff0c;如何批量去执行呢&#xff0c;这时候就可以利用反射里的func (v Value) Call(in []Value) []Value 方法。 // Call calls the function v with the input arguments in. // For example, if len(in)…...

Teleport

从官网中获取到的代码如下 App.vue <template><div class"outer"><h3>Tooltips with Vue 3 Teleport</h3><div><MyModal /></div></div> </template> <script setup> import MyModal from "./My…...

flutter与原生 相互通信实战

一、原生和flutter 通信 ios 通信类 CommonUtil.swift import Foundation import Flutterpublic class CommonUtil {public static func emitEvent(channel: FlutterMethodChannel, method: String, type: String, errCode: Int32?, errMsg: String?, data: Any?){safeMa…...

结构光相机原理

结构光相机原理...

ubuntu安装Anaconda

下载 Anaconda 进入 Ubuntu&#xff0c;自己新建下载路径&#xff0c;输入以下命令开始下载 注意&#xff0c;如果不是 x86_64&#xff0c;需要去镜像看对应的版本&#xff08;https://mirrors.bfsu.edu.cn/anaconda/archive/?CM&OA&#xff09; wget https://mirrors.…...

【RNA structures】RNA转录的重构和前沿测序技术

文章目录 RNA转录重建1 先简单介绍一下测序相关技术2 Map to Genome Methods2.1 Step1 Mapping reads to the genome2.2 Step2 Deal with spliced reads2.3 Step 3 Resolve individual transcripts and their expression levels 3 Align-de-novo approaches3.1 Step 1: Generat…...

4、Kafka 消费者

5.1 Kafka 消费方式 5.2 Kafka 消费者工作流程 5.2.1 消费者总体工作流程 5.2.2 消费者组原理 Consumer Group&#xff08;CG&#xff09;&#xff1a;消费者组&#xff0c;由多个consumer组成。形成一个消费者组的条件&#xff0c;是所有消费者的groupid相同。 • 消费者组内…...

CSS3 渐变

CSS3 渐变可以让你在两个或多个指定的颜色之间显示平稳的过渡。 CSS3渐变有两种类型&#xff1a;线性渐变&#xff08;Linear Gradients&#xff09;和径向渐变&#xff08;Radial Gradients&#xff09;。 线性渐变&#xff08;Linear Gradients&#xff09;&#xff1a; 线性…...

【Python 千题 —— 基础篇】分割有效信息

题目描述 题目描述 有时候我们需要截取字符串以获取有用的信息&#xff0c;比如对于字符串 “日期&#xff1a;2010-10-29”&#xff0c;我们需要截取后面的 10 个字符来获取日期&#xff0c;以便进行进一步分析。编写一个程序&#xff0c;输入一个字符串&#xff0c;然后输出…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...