字符串全排列问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4764 天前的主题，其中的信息可能已经有所发展或是发生改变。

假设有字符串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 条回复 • 1970-01-01 08:00:00 +08:00

dreampuf

2011-10-25 01:57:23 +08:00

单字符数组的笛卡尔积.

strs = "abc"

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

qiao

2011-10-25 02:34:47 +08:00

好久没写 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

2011-10-25 16:16:30 +08:00

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

qiao

2011-10-25 21:24:16 +08:00

@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

2011-10-26 19:49:42 +08:00

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

gfcheng

2011-11-03 20:57:33 +08:00

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

tsuibin

2012-01-18 12:12:13 +08:00

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