全排列问题

中午看到的一个题目。
求一个不重复字符串的全排列。

主要有递归，字典序等解决方案。然后想到stl里的next_permutation()函数，利用的便是字典序的方式。主要原理如下：

在当前序列中，从尾端往前寻找两个相邻元素，前一个记为i，后一个记为ii，并且满足i < ii。然后再从尾端寻找另一个元素j，如果满足i < *j，即将第i个元素与第j个元素对调，并将第ii个元素之后（包括ii）的所有元素颠倒排序，即求出下一个序列了。
在纸上画了半天，才把细节搞清楚了，确实很优雅的实现方式，很有启发性。

至于递归的方式，基于交换的思路，代码大体如下：

std::swap(val[i-1],val[k]);        
full_permutation(val,n,i+1);       
std::swap(val[i-1],val[k])  

看似很简单的三行，却很难模拟。
脑袋里想了半天，还是觉得很抽象。
不过这个算法最巧妙的地方还是利用字符串本身作为操作原型，没有引入其他结构存储字符串。

想来想去，觉得还是蛮复杂，遂自己写了一个python的版本，利用了yield特性，感觉好理解的多，如下：

def full_permutation(str):
    if (1 >= len(str)):
        yield str
    else:
        for i in full_permutation(str[1:]):
            for j in range(len(i) + 1):
                yield i[0:j] + str[0] + i[j:]   

只有7行。
思路也很简单，同样是利用递归的原理。
假如初始的字符串是a，字符串集合为{[a]}, 当加入b时，b的插入位置有a前和a后两个位置，插入后，新的字符串集合变为：
{[b, a], [a, b]}。当加入c时，对于[b, a]，c的插入位置有3个，b前，a前，a后，也就是说：
[b, a] + c => [c, b, a], [b, c, a], [b, a, c]，对于[a, b]也是同理。
概括来说，就是将每一个字符，插入每一个可能的位置。
(原文时间2013-9-16)