全排列的不同写法(茴字的不同写法)及对应的时间开销
资源课件:
- CS106B-recursion-ppt
- stanford library-timer.h
- stanford library-set.h
不同的方法
1------
Set<string> permutations1Rec(string remaining) {Set<string> res;if(remaining.size() == 0) {res += "";}else {for(int i = 0; i < remaining.size(); ++i) {char selectCharacter = remaining[i];string newRemaining = remaining.substr(0, i) + remaining.substr(i+1);Set<string> subres = permutations1Rec(newRemaining);for(auto str : subres) {res += selectCharacter + str;}}}return res;
}void permutations1(const string &str) {Set<string> res = permutations1Rec(str);cout << res << endl;
}
2------
Set<string> permutations2Rec(string remaining) {Set<string> res;if(remaining.size() == 0) {res += "";}else {char firstCharacter = remaining[0];string newRemaining = remaining.substr(1);Set<string> subres = permutations2Rec(newRemaining);for(string subpermutation : subres) {for(int i = 0; i <= subpermutation.size(); ++i) {string subpermutationCp = subpermutation;subpermutationCp.insert(subpermutationCp.begin() + i, firstCharacter);res += subpermutationCp;}}}return res;
}void permutations2(const string &str) {Set<string> res = permutations2Rec(str);cout << res << endl;
}
3------
Set<string> permutations3Rec(string str, int pos) {Set<string> res;if(pos == str.size()) {res += str;}else {for(int i = pos; i < str.size(); ++i) {if(i == pos || str[i] != str[pos]) {swap(str[i], str[pos]);res += permutations3Rec(str, pos+1);swap(str[i], str[pos]);}}}return res;
}void permutations3(const string &str) {Set<string> res = permutations3Rec(str, 0);cout << res << endl;
}
4------
Set<string> permutations4Rec(string remaining,string alreadyMade) {Set<string> res;if(remaining.size() == 0) {res += alreadyMade;}else {for(int i = 0; i < remaining.size(); ++i) {string newRemaining = remaining.substr(0, i) + remaining.substr(i+1);res += permutations4Rec(newRemaining, alreadyMade+remaining[i]);}}return res;
}void permutations4(const string &str) {Set<string> res = permutations4Rec(str, "");cout << res << endl;
}
运行代码
其中X为不同写法,permutationsXRec为具体实现函数,permutationsX为wrapper 函数。
#include <iostream>
#include "set.h"
#include "timer.h"
using namespace std;Set<string> permutations1Rec(string remaining) {Set<string> res;if(remaining.size() == 0) {res += "";}else {for(int i = 0; i < remaining.size(); ++i) {char selectCharacter = remaining[i];string newRemaining = remaining.substr(0, i) + remaining.substr(i+1);Set<string> subres = permutations1Rec(newRemaining);for(auto str : subres) {res += selectCharacter + str;}}}return res;
}void permutations1(const string &str) {Set<string> res = permutations1Rec(str);cout << res << endl;
}Set<string> permutations2Rec(string remaining) {Set<string> res;if(remaining.size() == 0) {res += "";}else {char firstCharacter = remaining[0];string newRemaining = remaining.substr(1);Set<string> subres = permutations2Rec(newRemaining);for(string subpermutation : subres) {for(int i = 0; i <= subpermutation.size(); ++i) {string subpermutationCp = subpermutation;subpermutationCp.insert(subpermutationCp.begin() + i, firstCharacter);res += subpermutationCp;}}}return res;
}void permutations2(const string &str) {Set<string> res = permutations2Rec(str);cout << res << endl;
}Set<string> permutations3Rec(string str, int pos) {Set<string> res;if(pos == str.size()) {res += str;}else {for(int i = pos; i < str.size(); ++i) {if(i == pos || str[i] != str[pos]) {swap(str[i], str[pos]);res += permutations3Rec(str, pos+1);swap(str[i], str[pos]);}}}return res;
}void permutations3(const string &str) {Set<string> res = permutations3Rec(str, 0);cout << res << endl;
}Set<string> permutations4Rec(string remaining,string alreadyMade) {Set<string> res;if(remaining.size() == 0) {res += alreadyMade;}else {for(int i = 0; i < remaining.size(); ++i) {string newRemaining = remaining.substr(0, i) + remaining.substr(i+1);res += permutations4Rec(newRemaining, alreadyMade+remaining[i]);}}return res;
}void permutations4(const string &str) {Set<string> res = permutations4Rec(str, "");cout << res << endl;
}int main() {Timer tim;tim.start();cout << "....." << endl;tim.stop();cout << "The code took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations1("123");tim.stop();cout << "The code took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations2("123");tim.stop();cout << "The code took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations3("123");tim.stop();cout << "The code took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations4("123");tim.stop();cout << "The code took " << tim.elapsed() << "ms to finish." << endl;return 0;
}
…
The code took 34ms to finish.
{“123”, “132”, “213”, “231”, “312”, “321”}
The code took 2ms to finish.
{“123”, “132”, “213”, “231”, “312”, “321”}
The code took 2ms to finish.
{“123”, “132”, “213”, “231”, “312”, “321”}
The code took 2ms to finish.
{“123”, “132”, “213”, “231”, “312”, “321”}
The code took 3ms to finish.
时间测试(非正式)
int main() {Timer tim;tim.start();cout << "....." << endl;tim.stop();cout << "The code took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations1("12345678");tim.stop();cout << "The code-1 took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations2("12345678");tim.stop();cout << "The code-2 took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations3("12345678");tim.stop();cout << "The code-3 took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations4("12345678");tim.stop();cout << "The code-4 took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations1("12345678");tim.stop();cout << "The code-1 took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations2("12345678");tim.stop();cout << "The code-2 took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations3("12345678");tim.stop();cout << "The code-3 took " << tim.elapsed() << "ms to finish." << endl;tim.start();permutations4("12345678");tim.stop();cout << "The code-4 took " << tim.elapsed() << "ms to finish." << endl;return 0;
}
The code took 38ms to finish.
The code-1 took 1150ms to finish.
The code-2 took 279ms to finish.
The code-3 took 1077ms to finish.
The code-4 took 1135ms to finish.
The code-1 took 1141ms to finish.
The code-2 took 279ms to finish.
The code-3 took 1071ms to finish.
The code-4 took 1129ms to finish.
感受
- 其实第一种方法和第四种方法它们思想是几乎一致的,从时间上它们也很接近。
- 第三种方法比1、4快些,但是函数调用依旧在
for
循环里,开销较大。 - 第二种方法函数调用在
for
循环外面,节省了很多时间。似乎也更好理解一些? - 这里纯属娱乐,学的比较晕,记录一下~
相关文章:

全排列的不同写法(茴字的不同写法)及对应的时间开销
资源课件: CS106B-recursion-pptstanford library-timer.hstanford library-set.h 不同的方法 1------ Set<string> permutations1Rec(string remaining) {Set<string> res;if(remaining.size() 0) {res "";}else {for(int i 0; i <…...
权衡后台数据库设计中是否使用外键
目录 引言 外键简介 对比 真实后台项目中的权衡 结论 引言 在大学学习数据库课程时,我们会早早的接触到外键这一概念,同时我相信大部分人在懂了外键的概念后都会觉得外键很重要,在涉及多表一定要用,但后来在我接触到真实项目…...

ChatGPT提示词方法的原理
关于提示词,我之前的一些文章可以参考: 【AIGC】AI作图最全提示词prompt集合(收藏级)https://giszz.blog.csdn.net/article/details/134815245?ydrefereraHR0cHM6Ly9tcC5jc2RuLm5ldC9tcF9ibG9nL21hbmFnZS9hcnRpY2xlP3NwbT0xMDExL…...

计算机网络 谢希仁(001-1)
计算机网络-方老师 总时长 24:45:00 共50个视频,6个模块 此文章包含1.1到1.4的内容 简介 1.1计算机网络的作用 三网融合(三网合一) 模拟信号就是连续信号 数字信号是离散信号 1.2互联网概述 以前2兆带宽就要98 现在几百兆带宽也就几百块 …...

Windows,MacOS,Linux下载python并配置环境图文讲解
Windows 打开python官网 点击download 点击黄色按钮 另存为 打开文件 全选 配置安装路径 安装中 关闭路径长度限制 完成 验证 同时按住winr(win就是空格键左边的东西) 输入cmd 键入python,如果出现版本(红框)即安装成功 MacOS 同理打开python官网 点击最新版本 拖…...

汽车网络基础知识 要点
在以太网开发中,常常会听到一些专业名词,例如PHY,MAC,MII,switch,下面是解释 PHY PHY 是物理接口收发器,它实现物理层。包括 MII/GMII (介质独立接口) 子层、PCS (物理编码子层) 、PMA (物理介…...

ClickHouse中的设置的分类
ClickHouse中的各种设置 ClickHouse中的设置有几百个,下面对这些设置做了一个简单的分类。...

香港空间服务器带宽和流量限制:原因和解决方法
香港空间服务器,也被称作香港虚拟服务器。一般情况下,香港空间服务器所提供的流量或者带宽,是足以满足99%的普通中小网站用户使用的,但也不排除,网站访问量大,租香港空间不能够满足要求的情况。 在本…...

echarts实践总结(常用一):柱状图(特点:渐变色、点击缩放、左右滑动、悬浮展示样式)
目录 第一章 echarts基本使用 第二章 echarts实践——柱状图 效果展示 第一章 echarts基本使用 Echarts常用配置项(详细入门)_echarts配置项手册-CSDN博客 第二章 echarts实践——柱状图 最近接到这么一个需求,需要画页面,然后有这么几个echarts的图需…...

CVE-2020-6418:Incorrect side effect modelling for JSCreate
文章目录 环境搭建漏洞分析漏洞利用漏洞触发链RCE 总结参考 环境搭建 sudo apt install python git reset --hard cecaa443ec29784ee26e31e678a333a3c1e71136 gclient sync -D// 手动引入漏洞,参考下面的 patch,把相关修改注释掉即可// debug version t…...

STM32信息安全 1.2 课程架构介绍:芯片生命周期管理与安全调试
STM32信息安全 1.2 课程架构介绍:STM32H5 芯片生命周期管理与安全调试 下面开始学习课程的第二节,简单介绍下STM32H5芯片的生命周期和安全调试,具体课程大家可以观看STM32官方录制的课程,链接:1.2. 课程架构介绍&…...

springboot278基于JavaWeb的鲜牛奶订购系统的设计与实现
鲜牛奶订购系统的设计与实现 摘 要 如今社会上各行各业,都喜欢用自己行业的专属软件工作,互联网发展到这个时候,人们已经发现离不开了互联网。新技术的产生,往往能解决一些老技术的弊端问题。因为传统鲜牛奶订购信息管理难度大&…...

SSH介绍及检测规则思路分析
一、SSH 1、定义 SSH是安全的加密协议,用于远程连接linux服务器。 2、ssh服务的主要功能: 1)提供远程链接服务器的功能; 2)对远程链接传输的数据进行加密 3、ssh与telnet的区别: 服务链接方式 服务数据…...
React核心⼊⻔-lesson1
自学React从入门到精通,从使用到写源码 React⼊⻔ 课堂⽬标资源起步 ⽂件结构⽂件结构⼀览React和ReactDomJSX 使⽤JSX组件 组件的两种形式 class组件function组件组件状态管理 类组件中的状态管理函数组件中的状态管理事件处理组件通信 Props属性传递contextredux⽣命周期 变…...

数据结构(三)——栈
三、栈、队列和数组 3.1 栈 3.1.1 栈的基本概念 线性表是具有相同数据类型的n(n≥0)个数据元素的有限 序列,其中n为表长,当n 0时线 性表是一个空表。若用L命名线性表,则其一般表示为 L (a1, a2, … , ai , ai1, ……...

【Redis知识点总结】(五)——Redis实现分布式锁
Redis知识点总结(五)——Redis实现分布式锁 setnxsetnx expiresetnx expire lua脚本set nx exset nx ex 随机值set nx ex 随机值 lua脚本set ex nx 随机值 lua脚本 锁续期RedissonRedLock 在Redis的众多应用场景中,分布式锁是Redis比…...

CSS 绝对定位 position:absolute
什么是CSS绝对定位absolute定位? 绝对定位absolute定位是CSS中的一种定位方式,可以将元素精确定位到一个确定的点,这与元素在文档流上的自然位置无关。相比起其他定位方式,绝对定位很灵活性,它可以将元素脱离文档流&am…...

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:RelativeContainer)
相对布局组件,用于复杂场景中元素对齐的布局。 说明: 该组件从API Version 9开始支持。后续版本如有新增内容,则采用上角标单独标记该内容的起始版本。 规则说明 容器内子组件区分水平方向,垂直方向: 水平方向为left&…...
Android制作微信添加多个图片,放大图片
1.添加依赖 implementation com.github.bumptech.glide:glide:4.12.0 //裁剪图片等等 implementation androidx.recyclerview:recyclerview:1.1.0 //recycleview依赖 2.使用recycleview <androidx.recyclerview.widget.RecyclerViewandroid:id"id/recyclerView"…...
iOS runtime理解和应用场景
一、runtime的动态性 OC的运行时系统(Runtime System)提供了丰富的动态特性,包括类与对象的创建、消息发送与转发、方法的动态添加与替换、属性的动态合成等。通过使用运行时库提供的API,可以在运行时获取和操作类与对象的信息,实现各种动态性的功能。 我对 Runtime 的理…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...

Python训练营-Day26-函数专题1:函数定义与参数
题目1:计算圆的面积 任务: 编写一个名为 calculate_circle_area 的函数,该函数接收圆的半径 radius 作为参数,并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求:函数接收一个位置参数 radi…...
文件上传漏洞防御全攻略
要全面防范文件上传漏洞,需构建多层防御体系,结合技术验证、存储隔离与权限控制: 🔒 一、基础防护层 前端校验(仅辅助) 通过JavaScript限制文件后缀名(白名单)和大小,提…...

Selenium 查找页面元素的方式
Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素,以下是主要的定位方式: 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...
java+webstock
maven依赖 <dependency><groupId>org.java-websocket</groupId><artifactId>Java-WebSocket</artifactId><version>1.3.5</version></dependency><dependency><groupId>org.apache.tomcat.websocket</groupId&…...
LeetCode 0386.字典序排数:细心总结条件
【LetMeFly】386.字典序排数:细心总结条件 力扣题目链接:https://leetcode.cn/problems/lexicographical-numbers/ 给你一个整数 n ,按字典序返回范围 [1, n] 内所有整数。 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。…...

多模态学习路线(2)——DL基础系列
目录 前言 一、归一化 1. Layer Normalization (LN) 2. Batch Normalization (BN) 3. Instance Normalization (IN) 4. Group Normalization (GN) 5. Root Mean Square Normalization(RMSNorm) 二、激活函数 1. Sigmoid激活函数(二分类&…...