字符串全排列问题

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 5342 days ago, the information mentioned may be changed or developed.

假设有字符串abc，那么写段程序打印出abc这三个字符组成的所有排列方式
比如:
abc
acb
bca
bac
cab
cba
如果是baa，则所有的排列组合应该是
baa
aba
aab
这就要考虑到一个重复字符的问题
第一个问题已经解决了，但是第二个问题今天弄了一天也没想出好办法

最后通过计算组合的hash，通过查询hash表的方式临时解决了
C++ 源码见连接 http://hi.baidu.com/tsuibin/blog/item/e9a044efe9692be7b2fb953e.html

不知道有没有人知道更好的方法

abc

Hash

baa

7 replies • 1970-01-01 08:00:00 +08:00

dreampuf

Oct 25, 2011

单字符数组的笛卡尔积.

strs = "abc"

strs_args = strs * len(strs)
for i in itertools.product(*strs_args):
print "".join(i)

qiao

Oct 25, 2011

好久没写 C++ 了：

<pre>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

template <typename T>
void permutation(T t, void (*fn)(const T &)) {
sort(t.begin(), t.end());
do {
fn(t);
} while(next_permutation(t.begin(), t.end()));
}

void print(const string &s) {
cout << s << endl;
}

int main() {
string s("baa");
permutation(s, print);
return 0;
}
</pre>

tsuibin

Oct 25, 2011

@qiao
这个问题的关键就是要自己实现 next_permutation（）这个函数啊

qiao

Oct 25, 2011

@tsuibin

每次记录一下被交换的元素即可：

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void permutation_helper(string &str, int start, int end) {
if (start == end) {
cout << str << endl;
} else {
bool visited[256];
fill(visited, visited + 256, false);
for (int i = start; i <= end; ++i) {
if (!visited[str[i]]) {
swap(str[start], str[i]);
permutation_helper(str, start + 1, end);
swap(str[start], str[i]);
visited[str[i]] = true;
}
}
}
}

void permutation(string str) {
sort(str.begin(), str.end());
permutation_helper(str, 0, str.length() - 1);
}

int main() {
string s("aab");
permutation(s);
return 0;
}

tsuibin

Oct 26, 2011

@qiao
great!
这个方法比我在STL源码刨析 (第380页) 看的next_permutation的实现源码更加简洁！

gfcheng

Nov 3, 2011

@tsuibin
多加个数组b做参数，保存结果（全排列），可以吗?
permutation(a, start, end,b):
if start == end:
c = "".join(a)
if c not in b:
b.append(c)
print c

tsuibin

Jan 18, 2012

@gfcheng 这样的话，如果数据中有重复的，你就不会将它加入到b了，但是需要考虑字符串中有重复的情况