当前位置: 首页 > 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 的理…...

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&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

实战三:开发网页端界面完成黑白视频转为彩色视频

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

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...

Selenium 查找页面元素的方式

Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素&#xff0c;以下是主要的定位方式&#xff1a; 基本定位方式 通过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.字典序排数&#xff1a;细心总结条件 力扣题目链接&#xff1a;https://leetcode.cn/problems/lexicographical-numbers/ 给你一个整数 n &#xff0c;按字典序返回范围 [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&#xff08;RMSNorm&#xff09; 二、激活函数 1. Sigmoid激活函数&#xff08;二分类&…...