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

全排列的不同写法(茴字的不同写法)及对应的时间开销

资源课件:

  1. CS106B-recursion-ppt
  2. stanford library-timer.h
  3. 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循环外面,节省了很多时间。似乎也更好理解一些?
  • 这里纯属娱乐,学的比较晕,记录一下~

相关文章:

全排列的不同写法(茴字的不同写法)及对应的时间开销

资源课件&#xff1a; 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 <…...

权衡后台数据库设计中是否使用外键

目录 引言 外键简介 对比 真实后台项目中的权衡 结论 引言 在大学学习数据库课程时&#xff0c;我们会早早的接触到外键这一概念&#xff0c;同时我相信大部分人在懂了外键的概念后都会觉得外键很重要&#xff0c;在涉及多表一定要用&#xff0c;但后来在我接触到真实项目…...

ChatGPT提示词方法的原理

关于提示词&#xff0c;我之前的一些文章可以参考&#xff1a; 【AIGC】AI作图最全提示词prompt集合&#xff08;收藏级&#xff09;https://giszz.blog.csdn.net/article/details/134815245?ydrefereraHR0cHM6Ly9tcC5jc2RuLm5ldC9tcF9ibG9nL21hbmFnZS9hcnRpY2xlP3NwbT0xMDExL…...

计算机网络 谢希仁(001-1)

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

Windows,MacOS,Linux下载python并配置环境图文讲解

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

汽车网络基础知识 要点

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

ClickHouse中的设置的分类

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

香港空间服务器带宽和流量限制:原因和解决方法

​  香港空间服务器&#xff0c;也被称作香港虚拟服务器。一般情况下&#xff0c;香港空间服务器所提供的流量或者带宽&#xff0c;是足以满足99%的普通中小网站用户使用的&#xff0c;但也不排除&#xff0c;网站访问量大&#xff0c;租香港空间不能够满足要求的情况。 在本…...

echarts实践总结(常用一):柱状图(特点:渐变色、点击缩放、左右滑动、悬浮展示样式)

目录 第一章 echarts基本使用 第二章 echarts实践——柱状图 效果展示 第一章 echarts基本使用 Echarts常用配置项(详细入门)_echarts配置项手册-CSDN博客 第二章 echarts实践——柱状图 最近接到这么一个需求&#xff0c;需要画页面&#xff0c;然后有这么几个echarts的图需…...

CVE-2020-6418:Incorrect side effect modelling for JSCreate

文章目录 环境搭建漏洞分析漏洞利用漏洞触发链RCE 总结参考 环境搭建 sudo apt install python git reset --hard cecaa443ec29784ee26e31e678a333a3c1e71136 gclient sync -D// 手动引入漏洞&#xff0c;参考下面的 patch&#xff0c;把相关修改注释掉即可// debug version t…...

STM32信息安全 1.2 课程架构介绍:芯片生命周期管理与安全调试

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

springboot278基于JavaWeb的鲜牛奶订购系统的设计与实现

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

SSH介绍及检测规则思路分析

一、SSH 1、定义 SSH是安全的加密协议&#xff0c;用于远程连接linux服务器。 2、ssh服务的主要功能&#xff1a; 1&#xff09;提供远程链接服务器的功能&#xff1b; 2&#xff09;对远程链接传输的数据进行加密 3、ssh与telnet的区别&#xff1a; 服务链接方式 服务数据…...

React核心⼊⻔-lesson1

自学React从入门到精通,从使用到写源码 React⼊⻔ 课堂⽬标资源起步 ⽂件结构⽂件结构⼀览React和ReactDomJSX 使⽤JSX组件 组件的两种形式 class组件function组件组件状态管理 类组件中的状态管理函数组件中的状态管理事件处理组件通信 Props属性传递contextredux⽣命周期 变…...

数据结构(三)——栈

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

【Redis知识点总结】(五)——Redis实现分布式锁

Redis知识点总结&#xff08;五&#xff09;——Redis实现分布式锁 setnxsetnx expiresetnx expire lua脚本set nx exset nx ex 随机值set nx ex 随机值 lua脚本set ex nx 随机值 lua脚本 锁续期RedissonRedLock 在Redis的众多应用场景中&#xff0c;分布式锁是Redis比…...

CSS 绝对定位 position:absolute

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

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:RelativeContainer)

相对布局组件&#xff0c;用于复杂场景中元素对齐的布局。 说明&#xff1a; 该组件从API Version 9开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 规则说明 容器内子组件区分水平方向&#xff0c;垂直方向&#xff1a; 水平方向为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&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

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

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

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

回溯算法学习

一、电话号码的字母组合 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是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...