全排列的不同写法(茴字的不同写法)及对应的时间开销
资源课件:
- 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 的理…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...