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

资源课件：

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循环外面，节省了很多时间。似乎也更好理解一些？
• 这里纯属娱乐，学的比较晕，记录一下～