浅谈生成全排列的4种方法

方法一:最简单的方法,直接使用STL中的next_permutation函数生成排列

 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    char res[] = "ABCD";
    do{
        puts(res);
    }while(next_permutation(res, res+4));
    return 0;
}

方法二:采用递归的思想解决,先输出所有以A开头的排列,然后输出以B开头的排列,接着输出…,最后输出以N开头的排列。以A开头的排列中,第一位是A,后面是B~N的排列。以AB开头的排列中,第一位是A,第二位是B,后面是C~N的排列……如此递归,生成的是按照字典序排列的全排列。

 

 

#include <bits/stdc++.h>
using namespace std;

int n;
char table[] = "ABCDEFGHIJK";
char res[1024];

void solve(int cur)
{
    if(cur == n){
        res[cur] = 0;
        puts(res);
        return ;
    }
    for(int i = 0; i < n; i++){
        bool ok = true;
        for(int j = 0; j < cur; j++)
            if(table[i] == res[j])
                ok = false;
        if(ok){
            res[cur] = table[i];
            solve(cur+1);
        }
    }
}


int main()
{
    while(cin >> n)
        solve(0);
    return 0;
}

方法三:应该算是回溯法,在课堂上学到的,当时只是感觉用到了排列组合中的一些思想,后来才知道是回溯法。这种方法效率应该最高,但是生成的序列并不按照字典序排列。

首先选择在首位元素,分别A~N,选择方法是与第一位后面的元素交换,然后选择第二位元素,选择方法是与第二位后面的元素交换,如此递归进行……注意递归返回时要把交换过的变量交换回来。

#include <bits/stdc++.h>
using namespace std;

int n;
char res[] = "ABC";

void solve(int cur)
{
    if(cur == n){
        res[cur] = 0;
        puts(res);
        return ;
    }
    for(int j = cur; j < n; j++){
        swap(res[j], res[cur]);
        solve(cur+1);
        swap(res[j], res[cur]);
    }
}

int main()
{
    n = strlen(res);
    solve(0);
    return 0;
}

方法四:带标记的递归方法。这种方法递归排列是要记录下之前访问过的字母,避免了产生排列生成下一个字母时对前面的搜索避免的时间浪费。依然要注意标记要在递归返回时修改。

 

 

#include <bits/stdc++.h>
using namespace std;

int n;
char table[] = "ABCD";
char res[1024];
bool vis[1024];

void solve(int cur)
{
    if(cur == n){
        res[cur] = 0;
        puts(res);
        return ;
    }
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            res[cur] = table[i];
            vis[i] = true;
            solve(cur+1);
            vis[i] = false;
        }
    }
}

int main()
{
    n = strlen(table);
    memset(vis, false, sizeof(vis));
    solve(0);
    return 0;
}

 

 

欢迎留言