字符串全排列

墨蓝 2022-07-16 21:17 245阅读 0赞

一、字符串的排列  
用C++写一个函数, 如 vector Permutation(string str)，打印出 str 的全排列,如 abc 的全排列: abc, acb, bca, dac, cab, cba  
二、全排列的递归实现  
为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后，递归的代码就很容易写出来了：

#include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    void myPermutation(string &str, string::iterator it1, vector<string> &vstr)//str传递引用这里要注意
    {
        if (it1 == str.end())
        {
            vstr.push_back(str); 
        }
    
        for (string::iterator it = it1; it != str.end(); it++)
        {
            swap(*it1, *it);
            myPermutation(str, it1 + 1, vstr);
            swap(*it1, *it);
        }
    }
    
    vector<string> Permutation(string str)
    {
        vector<string> vstr;
        string::iterator it1 = str.begin();
    
        myPermutation(str, it1, vstr);
    
        return vstr;
    }
    
    //测试代码
    int main(void)
    {
        string str = "abc";
        vector<string> vstr;
    
        vstr = Permutation(str);
    
        for (auto i : vstr)
        {
            cout << i << endl;
        }
    
        system("pause");
        return 0;
    }

二、去掉重复的全排列的递归实现  
由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122，第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数与第三个数是不相同的，交换之后得到221。与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。

换种思维，对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。  
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。下面给出完整代码：

bool ifSwap(string::iterator begin, string::iterator end)
    {
        for (string::iterator it = begin; it != end; it++)
        {
            if (*it == *end)
            {
                return true;
            }
        }
    
        return false;
    }
    
    void myPermutation(string &str, string::iterator it1, vector<string> &vstr)
    {
        if (it1 == str.end())
        {
            vstr.push_back(str); 
        }
    
        for (string::iterator it = it1; it != str.end(); it++)
        {
            if (ifSwap(it1, it)==false)
            {
                swap(*it1, *it);
                myPermutation(str, it1 + 1, vstr);
                swap(*it1, *it);
            }
        }
    }
    
    vector<string> Permutation(string str)
    {
        vector<string> vstr;
        string::iterator it1 = str.begin();
    
        myPermutation(str, it1, vstr);
    
        return vstr;
    }
    //测试代码
    int main(void)
    {
        string str = "abcc";
        vector<string> vstr;
    
        vstr = Permutation(str);
    
        for (auto i : vstr)
        {
            cout << i << endl;
        }
    
        system("pause");
        return 0;
    }