美文网首页
1. 字符串的全排列(深搜、递归、非递归)

1. 字符串的全排列(深搜、递归、非递归)

作者: 鬼谷神奇 | 来源:发表于2016-02-24 10:13 被阅读773次

    一、深搜法

    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <fstream>
    
    using namespace std;
    
    string str;
    bool mark[100];
    int ans[100];
    void DFS(int pos, int num)
    {
        if(num == str.length())
        {
            for(int i = 0; i < num; ++i)
                cout << str[ans[i]];
            cout << endl;
    
            return;
        }
    
        for(int i = 0; i < str.length(); ++i)
        {
            if(mark[i] == true)
                continue;
            mark[i] = true;
            ans[num] = i;
            DFS(i, num+1);
            mark[i] = false;
        }
    }
    
    int main()
    {
        ifstream cin("in.txt");
    
        while(getline(cin, str))
        {
            sort(str.begin(), str.end());
    
            for(int i = 0; i < str.length(); ++i)
            {
                for(int j = 0; j < str.length(); ++j)
                {
                    ans[j] = 0;
                    mark[j] = false;
                }
    
                mark[i] = true;
                ans[0] = i;
                DFS(i, 1);
            }
            
        }
    
        return 0;
    }
    
    

    二、递归法

    对于包含重复字符的字符串的全排列,在使用递归法交换两个元素之前,需要判断是否需要交换。在from到to位置的元素中,如果存在与str[j]相同的元素,则不必交换

    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <fstream>
    
    using namespace std;
    
    string str;
    
    bool isSwap(int start, int pos)
    {
        for(int i = start; i < pos; ++i)
            if(str[i] == str[pos])
                return false;
        return true;
    }
    
    void CalcAllPermutation(string & str, int from, int to)
    {
        if(to <= 1)
            return;
        if(from == to)
            cout << str << endl;
        else
        {
            for(int i = from; i <= to; ++i)
            {
                if(isSwap(from, i))
                {
                    swap(str[i], str[from]);
                    CalcAllPermutation(str, from+1, to);
                    swap(str[i], str[from]);  //回溯
                }
                
            }
        }
    }
    
    int main()
    {
        ifstream cin("in.txt");
        while(getline(cin, str))
        {
            sort(str.begin(), str.end());
            CalcAllPermutation(str, 0, str.length()-1);
        }
    
        return 0;
    }
    

    三、STL next_permutation

    获取字典序的下一次全排列:

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
        int a[4] = {1, 2, 3, 4};
    
        next_permutation(a, a+4);
    
        //向后获取字典序的下一次全排列
        for(int i = 0; i < 4; ++i)
                cout << a[i] << " ";
        cout << endl;
    
        //向前获取字典序的上一次全排列
        prev_permutation(a, a+4);
        for(int i = 0; i < 4; ++i)
                cout << a[i] << " ";
        cout << endl;
    
    
        //获取所有全排列
        do{
            for(int i = 0; i < 4; ++i)
                cout << a[i] << " ";
            cout << endl;
        }while(next_permutation(a, a+4));
        
    
        return 0;
    }
    

    四、非递归法(即STL next_permutation 函数的实现)

    使用非递归法,要求我们实现的函数具有这样的功能:对于任一序列可以按照字典序计算出下一序列。如:21543的下一序列是23145,分四步:

    1. 从最右边开始比较两两相邻的元素,知道找到第一个升序的元素对,并记录元素对左边的元素a[i],当i<0时,结束(上例中找到的元素为1)
    2. 从最右边开始找到第一个比a[i]大的元素a[k](找到3)
    3. 交换a[i]和a[j](交换1和3)
    4. 把从i+1位到最后的元素翻转
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    bool calNextPermutation(int * a, int n)
    {
        //第一步
        for(int i = n-2; i >= 0 && a[i] > a[i+1]; --i)
        {
            ;
        }
    
        if(i < 0)
            return false;
    
        //第二步
        for(int k = n-1; k > i && a[k] <= a[i]; --k)
        {
            ;
        }
    
        //第三步
        swap(a[i], a[k]);
    
        //第四步
        reverse(a+k+1, a+n);
    
        return true;
    
    }
    
    int main()
    {
        int a[4] = {1, 2, 3, 4};
    
        //向后获取最近的一次全排列
        if(calNextPermutation(a, 4))
        {
            for(int i = 0; i < 4; ++i)
                cout << a[i] << " ";
            cout << endl;
        }
    }
    

    五、全排列的应用—八皇后问题

    题意:在8X8的国际象棋棋盘上摆放8个皇后,彼此之间不能相互攻击。即:8个皇后任意两个不能处于同一行、同一列、同一对角线。
    算法思想:使用maze[i] = j 表示第i行的皇后所在的列j,数组使用1-8初始化,递归求得数组元素的全排列,由于所有的皇后均不在同一行、同一列,所以,我们只需判断任意两个皇后是否在同一对角线上即可。

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int maze[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    int len;
    int cnt = 0;
    
    bool check()
    {
        for(int i = 1; i <= len; ++i)
            for(int j = i + 1; j <= len; ++j)
            {
                if(i-j == maze[i]-maze[j] || j-i == maze[i]-maze[j])
                    return false;
            }
    
        return true;    
    }
    
    void calPermutation(int * maze, int start)
    {
        if(start == len)
        {
            if(check())
            {
                cnt++;
                for(int i = 1; i <= len; ++i)
                    cout << maze[i];
                cout << endl;
            }
        }
        else
        {
            for(int i = start; i <= len; ++i)
            {
                swap(maze[start], maze[i]);
                calPermutation(maze, start+1);
                swap(maze[start], maze[i]);
            }
        }
        
    }
    
    int main()
    {
        len = sizeof(maze)/sizeof(int)-1;
        calPermutation(maze, 1);
        
        cout << cnt << endl;
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:1. 字符串的全排列(深搜、递归、非递归)

          本文链接:https://www.haomeiwen.com/subject/rfgbkttx.html