输出字符串的全排列

亦凉 2022-07-16 01:50 163阅读 0赞

参考文章：[http://blog.csdn.net/hackbuteer1/article/details/7462447][http_blog.csdn.net_hackbuteer1_article_details_7462447]

全排列就是从第一个数字起每个数分别与它后面的数字交换

#include<iostream>
    using namespace std;
    #include<assert.h>
    
    void Permutation(char* pStr, char* pBegin)
    {
        assert(pStr && pBegin);
    
        if(*pBegin == '\0')
            printf("%s\n",pStr);
        else
        {
            for(char* pCh = pBegin; *pCh != '\0'; pCh++)
            {
                swap(*pBegin,*pCh);
                Permutation(pStr, pBegin+1);
                swap(*pBegin,*pCh);
            }
        }
    }
    
    int main(void)
    {
        char str[] = "abc";
        Permutation(str,str);
        return 0;
    }

如果考虑到有重复的字符串，则需要考虑重复的字符串。  
**去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换**

#include<iostream>
    using namespace std;
    #include<assert.h>
    
    //在[nBegin,nEnd)区间中是否有字符与下标为pEnd的字符相等
    bool IsSwap(char* pBegin , char* pEnd)
    {
        char *p;
        for(p = pBegin ; p < pEnd ; p++)
        {
            if(*p == *pEnd)
                return false;
        }
        return true;
    }
    void Permutation(char* pStr , char *pBegin)
    {
        assert(pStr);
    
        if(*pBegin == '\0')
        {
            static int num = 1;  //局部静态变量，用来统计全排列的个数
            printf("第%d个排列\t%s\n",num++,pStr);
        }
        else
        {
            for(char *pCh = pBegin; *pCh != '\0'; pCh++)   //第pBegin个数分别与它后面的数字交换就能得到新的排列 
            {
                if(IsSwap(pBegin , pCh))//判断从字符串开始到现在是否有重复的字符串
                {
                    swap(*pBegin , *pCh);
                    Permutation(pStr , pBegin + 1);
                    swap(*pBegin , *pCh);
                }
            }
        }
    }
    
    int main(void)
    {
        char str[] = "baa";
        Permutation(str , str);
        return 0;
    }

这是在牛客网上看到的一段显得很高端的代码

// 全排列问题 深搜 / 回溯
    
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    void dfs(vector<string > &res, string &num, string &cur, vector<bool> &vis)
    {
        int n = num.size();
        if (cur.size() == n)
        {
            res.push_back(cur);
            return;
        }
        for (int i = 0; i<n; i++)
        {
            if (vis[i] || (i && num[i - 1] == num[i] && vis[i - 1]))
                continue;
            cur.push_back(num[i]);
            vis[i] = true;
            dfs(res, num, cur, vis);
            vis[i] = false;
            cur.pop_back();
        }
    }
    
    vector<string> permute(string& nums) {
        vector<string > res;
        string cur;
        vector<bool> vis(nums.size(), false);
        sort(nums.begin(), nums.end());
        dfs(res, nums, cur, vis);
        return res;
    }
    
    int main(void)
    {
        string s;
        cin >> s;
        vector<string> strs = permute(s);
        for (auto v : strs)
            cout << v << endl;
    
        return 0;
    }

[http_blog.csdn.net_hackbuteer1_article_details_7462447]: http://blog.csdn.net/hackbuteer1/article/details/7462447