字符串全排列问题

[tsuibin]

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

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

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

[dreampuf]

单字符数组的笛卡尔积.

strs = "abc"

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

[qiao]

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

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

[qiao]

@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]

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

[gfcheng]

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

[tsuibin]

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