当前位置: 首页 > 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;然后输出…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...