c++ abcd....等等字符所有不同的非重复组合排布

比如abc的组合类型 abc acb bac bca cab cba.

分析: 我们当然可以写三个嵌套的for循环去取，但是如果是abcd的组合呢？还要修改代码添加一层for。那如果是n个字母呢？你又要手动添加多少层for呢？

所以需要一个忽视字母个数的实现。我们知道多层for(每次for里面的处理还类似)那么可以升华成递归调用。这里我们用递归解决。

以abc为例

(第一层递归里）取a，给第二层传bc进去(同时告诉第二层，截止第一层字符串组合是a)

（第二层递归里）取b，给第三层传c进去(同事告诉第三层，截止第二层字符串组合出的是ab)

(第三层递归里) 取c。发现这一层只有一个c可以取，那么在第二层字符串组合里面加入c，return。 ---->此时完成一种排列组合： abc

(第一层递归里）取a，给第二层传bc进去(同时告诉第二层，截止第一层字符串组合是a)

（第二层递归里）取c，给第三层传b进去(同事告诉第三层，截止第二层字符串组合出的是ac)

(第三层递归里) 取b。发现这一层只有一个b可以取，那么在第二层字符串组合里面加入b，return。 ---->此时完成一种排列组合: acb

(第一层递归里）取b，给第二层传ac进去(同时告诉第二层，截止第一层字符串组合是b)

（第二层递归里）取a，给第三层传c进去(同事告诉第三层，截止第二层字符串组合出的是ba)

(第三层递归里) 取c。发现这一层只有一个c可以取，那么在第二层字符串组合里面加入c，return。 ---->此时完成一种排列组合：bac

.........

..........

可以看到上面的设计是可以把所有排列都取到的。那么接下来是代码实现:

#include<iostream>
#include<list>
#include<vector>
#include<string>
using namespace std;

//最开始变量用的vector<char>,后面发现要删除元素，vector效率低，list效率高。要修改的话，每一个vector<char>都要改成list<char>好烦啊。这里统一用个别名，以后就可以只修改这里就好了。
typedef list<char> AlpContainer;  

//Alps:这层可用的字母集， strs:用来记录所有完成的字母组合， preStr:上一层搞出来的字母组合
void getCurAlphabet(const AlpContainer& Alps, vector<string>& strs, const string& preStr) 
{
    if (Alps.size() == 1) //最后一层的话，把组合成型的字母组合记录下来
    {
        AlpContainer::const_iterator it = Alps.begin();
        
        string myCurStr(preStr);
        myCurStr += string(1,*it); //完成所有排布的字母组合
        
        strs.push_back(myCurStr);
        return;
    }
    
    for (AlpContainer::const_iterator it = Alps.begin();  it != Alps.end(); ++it) //这层从可用字母集中顺序挑一个字母出来
    {
        string myCurStr(preStr);
        myCurStr += string(1,*it); //到这层为止的字母组合

        AlpContainer sonAlps(Alps); //从可用字母中剃掉这层用了的字母
        sonAlps.remove(*it);

        getCurAlphabet(sonAlps, strs, myCurStr); //让下一层继续进行剩余字母的组合工作
    }
}

int main()
{
    AlpContainer objs;
    objs.push_back('a');
    objs.push_back('b');
    objs.push_back('c');
    objs.push_back('d');

    vector<string> result;
    string preStr;

    getCurAlphabet(objs, result, preStr);

    for(vector<string>::size_type i = 0; i < result.size(); ++i)
        cout << i+1 << " : " << result[i] << endl;
}