首页 > 试题广场 >

全排列

[编程题]全排列
  • 热度指数:23436 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z',而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入描述:
输入只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度在1到6之间。


输出描述:
输出这个字符串的所有排列方式,每行一个排列。要求字母序比较小的排列在前面。字母序如下定义:
已知S = s1s2...sk , T = t1t2...tk,则S < T 等价于,存在p (1 <= p <= k),使得
s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。

每组样例输出结束后要再输出一个回车。
示例1

输入

abc

输出

abc
acb
bac
bca
cab
cba

醉了,就因为少了最后一个换行卡了十分钟。。

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

string str;
string res;
bool used[6];

void Dfs(int cur)
{
    if (cur == str.length())
    {
        cout << res << endl;
        return;
    }
    for (int i = 0; i < str.length(); ++i)
    {
        if (!used[i])
        {
            //放入
            used[i] = true;
            res[cur] = str[i];
            Dfs(cur + 1);
            used[i] = false;
        }
    }
}

int main()
{
    while (cin >> str)
    {
        sort(str.begin(), str.end());
        res = str;
        memset(used, false, sizeof(used));
        Dfs(0);
        cout << endl;
    }
}
发表于 2019-06-05 21:12:03 回复(2)
#通过递归交换数组,得到一个无重复列表的全排列
#需要注意几点,输入字母未排序,输出最后还要加一个空格(应该是利于某些算法)

#这函数输入如果是有序的可以得到按顺序的全排列
def allPermute(array):
    result = []
    tempArray = list(array)
    def exchange(num):
        nonlocal tempArray
        nonlocal result
        if num == len(tempArray)-1:
             result.append(list(tempArray))
        else:
            for j in range(num,len(tempArray)):
                tempArray[num],tempArray[j] = tempArray[j],tempArray[num]
                exchange(num+1)
                tempArray[num], tempArray[j] = tempArray[j], tempArray[num]
    exchange(0)
    return result
try:
    while True:
        string = list(input())
        temp = allPermute(string)
        temp.sort()
        for i in temp:
            print("".join(i))
        print()
except Exception:
    pass

编辑于 2018-10-08 18:25:16 回复(0)
Java ,使用回溯
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    static  boolean[] visited;
    static char[] array;
    static  ArrayList<String> list = new ArrayList<>();
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        array = scanner.next().toCharArray();
        visited = new boolean[array.length];
        gen(0,"");
        Collections.sort(list);
        for (String s1 : list) System.out.println(s1);
        //注意题目要求:每组样例输出结束后要再输出一个回车。
        System.out.println();
    }
    
    static void gen(int step,String cur){
        // 递归终止
        if (step==array.length){
            list.add(cur);
            return;
        }
        for (int i = 0; i <array.length ; i++) {
            if (!visited[i]){
                visited[i]=true;
                gen(step+1,cur+array[i]);
                // 回溯,清除现场
                visited[i]=false;
            }
        }

    }
}


发表于 2020-03-19 09:40:23 回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stack>
#include <queue>
#include <math.h>
#include <functional>
using namespace std;
bool mark[10];
char Out[10]; 
char In[10];
int len;
void DFS(int num){
    if(num == len){ // 递归退出,0 - len-1位的字符已经就位,输出即可
        Out[num] = '\0';
        puts(Out);
        return;
    }
    for(int i = 0;i < len;i++){
        if(mark[i] == 1) continue; //使用过跳到下一次循环
        mark[i] = 1;
        Out[num] = In[i]; //加到输出字符数组
        DFS(num + 1);
        mark[i] = 0; //回溯
    }
}

int main(){
    while(gets(In)){
        len = strlen(In);
        sort(In,In + len); //给定的并没有排好序
        DFS(0);
        cout<<endl;
    }
    return 0;
}
发表于 2018-03-12 19:44:09 回复(1)
#include"iostream"
using namespace std;
void fP(string ipt, string flags, string res, int idx){
    if(idx== ipt.length()){cout<< res<< endl;}
    else{
        for(int i= 0; i< flags.length(); i++){
            if(flags[i]== '0'){
                res[idx]= ipt[i];flags[i]= '1';
                fP(ipt, flags, res, idx+ 1);
                flags[i]= '0';
            }
        }
    }
}
int main(){
    string ipt;
    while(cin>> ipt){
        fP(ipt, string(ipt.length(), '0'), string(ipt.length(), ' '), 0);
    }
}
发表于 2022-02-25 10:58:03 回复(1)
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int MAXN = 10;

bool visit[MAXN];     //字符串内某个字母是否被遍历过
char sequence[MAXN];  //结果

//全排列可以用一个树表示,index就表示当前所处在第几层
void GetPermutation(string str,int index){
    if(index == str.size()){
        for(int i=0;i<str.size();i++){
            printf("%c",sequence[i]);
        }
        printf("\n");
    }else{
        for(int i=0;i<str.size();i++){
            if(visit[i] == true){
                continue;
            }
            visit[i]=true;
            sequence[index]=str[i];
            GetPermutation(str,index+1);
            visit[i]=false;
        }

    }
    return;

}
int main()
{
    string str;
    while(cin>>str){
        sort(str.begin(),str.end());  //将字符串按照字典顺序排序
        GetPermutation(str,0);
        printf("\n");
    }
    return 0;
}

发表于 2021-03-07 21:14:30 回复(0)
排列树剪枝来生成全排列。
由于要求按照字典序输出,所以要先对输入的字符串进行排序,然后递归得到的全排列才是字典序的。
#include<bits/stdc++.h>

using namespace std;

const int maxn = 26;
int a[maxn];
bool vis[maxn];
string s;

void Print(int len)
{
    for(int i = 0;i < len; i++)
        cout << (char)a[i];
    cout << "\n";
}

void Search(int len, int cur)
{
    if(cur == len)     //递归边界
    {
        Print(len); return ;
    }
    else for(int i = 0;i < len; i++)
    {
        if(vis[i] == false)    //排列树剪枝
        {
            a[cur] = s[i]; vis[i] = true;
            Search(len, cur+1);
            vis[i] = false;     //回溯
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> s)
    {
        int len = s.length();
        fill(vis, vis+maxn, false);
        sort(s.begin(), s.end());
        Search(len, 0);
    }
    return 0;
}


编辑于 2021-01-18 13:57:10 回复(0)
#include <iostream>
(720)#include <string>
#include <vector>
using namespace std;
vector<string> v;
void dfs(int* flg,string str,int len){
    if(str.length()==len){
        v.push_back(str);
        return;
    }
    for(int i=0;i<300;i++){
        if(flg[i]==1){
            flg[i]=0;
            dfs(flg,str+char(i),len);
            flg[i]=1;
        }
    }
    return;
}

int flg[300];

int main(){
    string str;
    cin>>str;
    for(int i=0;i<str.length();i++) flg[str[i]]++;
    dfs(flg,"",str.length());
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<endl;
    }
    cout<<endl;
}
/*
题目有点问题:题目说a<b<...<A<B<...<Y<Z。但是实际上ascii码是大写字母排在前面。
按ascii码排序的话,如果sample里有大小写混合的字符串就会报错。
然而并没有。
要么是题目写错,要么是样例设计的不完整。
至于我,懒得改了。
*/
发表于 2020-04-15 12:17:11 回复(0)
c++使人进步 
//对于含重复元素的输入依然有效,且不会给出重复输出,e.g.输入aabc,不会输出两个aabc。ASCII码对应字符均可输入。
#include<bits/stdc++.h>
using namespace std;
map<char,int> m;
string s;
string res;
void getall(){
    if(res.size()==s.size()){
        cout<<res<<endl;
        return;
    }
    for(auto it=m.begin();it!=m.end();it++){//若使用for(auto it:m)来进行迭代(对应的it->second换成it.second)结果将是错误的,因为并非指针
        if(it->second>0){
            res.push_back(it->first);
            it->second--;
            getall();
            it->second++;
            res.pop_back();
        }
    }
}
int main(){
    cin>>s;
    for(int i=0;i<s.size();i++){
        m[s[i]]++;
    }
    getall();
    cout<<endl;
    return 0;
}


发表于 2020-03-28 12:05:07 回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(const void *a,const void *b) {
    return *(char*)a-*(char*)b;
}
int factorial(int n) {
    if(n==0) return 1;
    return n*factorial(n-1);
}
void all_sorts(char **list,int first,int n,int len) {
    if(n>=2) {
        all_sorts(list,first,n-1,len);
        int gap=factorial(n-1);
        for(int i=1; i<n; i++) {
            int site=first+gap*i;
            list[site]=(char*)malloc(sizeof(char)*7);
            int start=len-n;
            for(int j=0; j<start; j++) list[site][j]=list[first][j];
            list[site][start]=list[first][start+i];
            int top=start;
            for(int j=start; j<=len; j++) if(j!=start+i) list[site][++top]=list[first][j];
            all_sorts(list,site,n-1,len);
        }
    }
}
int main() {
    char str[7];
    while(scanf("%s",str)!=EOF) {
        int len=strlen(str);
        char **multilist=(char**)malloc(sizeof(char*)*factorial(len));
        qsort(str,len,sizeof(char),cmp);
        multilist[0]=str;
        all_sorts(multilist,0,len,len);
        for(int i=0; i<factorial(len); i++) printf("%s\n",multilist[i]);
        printf("\n");
    }
    return 0;
}


编辑于 2020-03-07 13:47:17 回复(0)
这题应该是要考察回溯法,可用递归完成。
发表于 2019-03-18 16:29:40 回复(0)
参考https://blog.csdn.net/beggar200/article/details/50245207


#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

bool next_perm(char *perm,int n){
    int i=n-2;
    while(i>=0&&perm[i]>perm[i+1])
        i--;   //find x
    if(i<0)
        return false;

    int j=n-1;
    while(j>i&&perm[j]<=perm[i])
        j--; //find y;

    swap(perm[i],perm[j]);
    reverse(perm+i+1,perm+n);
    return true;


}
int main(){
    char str[7];
    while(scanf("%s",str)!=EOF){
        int n=strlen(str);
        sort(str,str+n);
        printf("%s\n",str);
        while(next_perm(str,n))
            printf("%s\n",str);
        printf("\n");
        
    }

}

发表于 2019-03-06 12:39:08 回复(1)
#include <stdio.h>
#include <string.h>
char sort[720][7];
int n = 0;
void swap(char *p, int i, int j)
{
    char t = p[i];
    p[i] = p[j];
    p[j] = t;
}
void resort(char str[][7])
{
    char temp[7];
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(strcmp(str[i],str[j]) > 0)
            {
                strcpy(temp, str[i]);
                strcpy(str[i], str[j]);
                strcpy(str[j], temp);
            }
        }
    }
}
//全排列
void permutation(char *p, int from, int to)
{
    if(from == to)
    {
        strcpy(sort[n++], p);
        return;
    }
    for(int i = from; i <= to; i++)
    {
        swap(p, from, i);
        permutation(p, from + 1, to);
        swap(p, from, i);//换回来
       
    }
}
int main()
{
    char p[6];
    scanf("%s", p);
    permutation(p,0,strlen(p)-1);
    resort(sort);
    for(int i = 0; i < n; i++)
    {
        printf("%s\n", sort[i]);
    }
    printf("\n");
    return 0;
}
发表于 2019-01-31 17:10:14 回复(1)
#include<iostream>
#include<algorithm>
using namespace std;
void f(string pre, string s){
    if(pre.size()==s.size()){cout<<pre<<endl;return;}
    for(int i=0;i<s.size();i++){
        int ok=1;
        for(int j=0;j<pre.size();j++){
            if(pre[j]==s[i]){ok=0;break;}
        }
        if(ok)f(pre+s[i], s);
    }
}
int main(){
    string s;
    while(cin>>s){
        sort(s.begin(),s.end());
        f("", s);
        cout<<endl;
    }
    return 0;
}

发表于 2018-05-10 22:46:52 回复(0)
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int size;
char str[7];
bool mark[7];
char ans[7];
void DFS(int num){
 if(num==size){
  puts(ans);
  return;
 }
 int i;
 for(i=0;i<size;i++){
  if(mark[i]==false){
   ans[num]=str[i];
   mark[i]=true;
   DFS(num+1);
   mark[i]=false;
  }
 }
 
}
int main(){
 while(scanf("%s",str)!=EOF){
  int i;
  for(i=0;i<7;i++)
  mark[i]=false;
  size=strlen(str);
  sort(str,str+size);
  DFS(0);
  printf("\n");
 }
 return 0;
}

编辑于 2018-03-06 22:39:40 回复(0)
#include<iostream>
#include <vector>
#include <algorithm>
#include<string>
using namespace std;
class Solution {
public:
     vector<string> Permutation(string str) {
          if(str!="") {
              sort(str.begin(),str.end());//保证了字典序输出,因为abc,一次交换是bac,不恢复状态,所以下次交换是cab。
              dfs(str,0);
          }
          return result;
     }
     void Print(){
          for(int i=0;i<result.size();i++){
              cout<<result[i]<<endl;
          }
     }
private:
     void dfs(string str,int s){
          int sz = str.size();
          if(s==str.size()){
              result.push_back(str);
              return;
          }
          for(int i=s;i<sz;++i){
              if(i!=s&&str[i]==str[s]) continue;
              swap(str[i],str[s]);
              dfs(str,s+1);
          }
     }
     vector<string> result;
};
int main(){
    string str;
    cin >> str;

     Solution sol;
     sol.Permutation(str);//不加sort"acb"会不按照字典序输出
     sol.Print();
    return 0;
} 
请问:下面是哪里有问题?没看懂啥意思。。
答案错误:您提交的程序没有通过所有的测试用例
case通过率为0.23%

测试用例:
Bc1:98,c2:03
dbc

对应输出应该为:

bc

你的输出为:
空。请检查一下你的代码,有没有循环输入处理多个case。

发表于 2017-08-29 12:25:51 回复(1)
本人自己写的代码:
/**
*八皇后问题,使用递归的方法来解
*怎么说呢,萌新觉得这题递归的写法和玛雅人的密码那题挺像的(我抄别人的代码)
*萌新就是一张白纸,觉得这种递归很神奇,理由如下
*①递归中使用全局数组,大家一起用一个,每次递归结束后都要恢复全局变量为原值
*②递归中使用一个循环这个我也觉得很骚,印象中自己只会那种if return的语句模式的
*根据数列递推公式写的递归函数
*其他类型语句出现在递归函数中,萌新觉得很神奇。
*在玛雅人的密码那题中,是不断的移位,设置移位的标志变量flag[]来记录是否移位,
*如果已经移位了的话就不对节点进行扩展
*本题中,通过设置标志变量数组flag[]来记录当前字符是否被使用过,
*如果使用过了的话就继续寻找,结果是存在一个全局字符数组res中
*我们可以仔细的思考一下res可能的作用域,
*它的作用域范围绝对不可能是在递归函数里面,
*因为如果在递归函数里声明它的话,递归子层也会声明一个这个数组,
*那么无法做到所有的递归函数都使用同一个数组。
*实际上对于老手来说,他们都不会思考这种萌新才想的事情
*因为不同层的递归都要对这个结果数组进行写操作,
*换言之,它必须被所有层的递归函数共享
*除了全局变量,还有谁能做到这一点???还有谁???
*当然还有另一种放法,在main函数中定义res,
*将它作为参数传给递归函数,递归函数再把res传给它调用的递归函数
*既然是全局变量,那又可以思考一个问题,为什么同样是全局变量,
*凭什么flag[]这个标志数组要还原为原来的值,而res不用
*玛雅人的密码那题,它的循环部分的代码:
*flag[]和str都是全局变量,都需要还原
    for(i=0;i<n-1;i++)//从头开始,挨个交换
    {
        if(flag[i]==0)
        {
            swap(&str[i],&str[i+1]);//交换过后,下次就不再交换,
                        //如ab 交换后为ba,若不标记下次就有要交换成ab
            flag[i]=1;//将该位置标记
            find(str,n,k+1);//此次交换过后,k++,进行下一轮判定
            swap(&str[i],&str[i+1]);//返回原状
            flag[i]=0;
        }
    }
*理由是str必须要还原,str是搜索过程中前后连贯使用的变量,必须还原
*而res是记录结果的数组,必然不能还原,需求不同,没有比较的必要哈哈
*/
/**
*解题调试过程:
*->编码
*->检查:
*    ①发现忘记将输入的字符进行排序qsort();
*    ②cmp的返回值有问题,忘记了传进来的是指针不是值,不能直接相减
*    ③cur未在main函数中清0,(通过思考res数组的初始值发现)
*    ④
*->编译:
*    错误:新增加的cur= 0;语句的分号达成了中文的分号,产生理由:不详
*    影响:2处error
*    修改后,自测实例通过
*->提交:输出格式不符合要求
*    查看别人的代码,发现每组样例输出结束后要再输出一个回车
*    理解错了样例的意思,以为是每一个排列
*    通过啦!!!开森,回宿舍洗澡去!!!
*/
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
int flag[6];
char res[7];
char ori[7];
int cmp(const void * p1, const void *p2){
    char * c1 = (char *)p1;
    char * c2 = (char *)p2;
    return (*c1 - *c2);//低类型可以自动转化为高类型,不需要(int)进行强制类型转换
}
int cur = 0;
/**
*深入优先搜索的递归算法
*参数:当前的深度,同时也作为数组的下标
*当然深度也可以作为全局变量,在递归调用后恢复原值
*那我就不要参数,使用后一个方法吧
*/
void DFS(){
    int len = strlen(ori);//其实len是一直不变的,
              //作为全局变量的话可以减少strlen()运算
         //不过全局变量的缺点是访问速度不如局部变量快,我暂时是这么认为的
    if(cur == len){ //递归的退出条件,当下标=(strlen(ori) - 1)+1
                    //这么写是为了表示字符串已经存完了,
                              //该存'\0'了,不存'\0'就不是字符串
                    //用%s输出就会出错啦
        res[cur] = '\0';
        printf("%s\n", res);
        return ;
    }
    int i;
    for(i = 0; i < len; i++){
        if(!flag[i]){ //如果没有被标记,元素未被使用
            flag[i] = 1;
            res[cur] = ori[i];
            cur ++;
            DFS();
            cur --;
            flag[i] = 0;
        }
    }
}
int main(){
    int n;
    while(scanf("%s", ori) != EOF){
        n = strlen(ori);
        cur = 0;
        qsort(ori, n, sizeof(char), cmp);
        while(n--) flag[n] = 0;
        DFS();
        printf("\n");
    }
    return 0;
}
我参考的是Frostime的代码,并在编制上述计算机程序解决问题前,通过此代码,熟悉了一下深度优先搜索的递归函数的运算过程。
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
 
string str;
string res;
bool used[6];
 
void Dfs(int cur)
{
    if (cur == str.length())
    {
        cout << res << endl;
        return;
    }
    for (int i = 0; i < str.length(); ++i)
    {
        if (!used[i])
        {
            //放入
            used[i] = true;
            res[cur] = str[i];
            Dfs(cur + 1);
            used[i] = false;
        }
    }
}
 
int main()
{
    while (cin >> str)
    {
        sort(str.begin(), str.end());
        res = str;
        memset(used, false, sizeof(used));
        Dfs(0);
        cout << endl;
    }
}

输入为abc运行的部分过程:


编辑于 2019-06-26 22:27:49 回复(9)
用STL中的全排列。
#include <bits/stdc++.h>
using namespace std;
int main(){
    for(string s;cin>>s;cout<<endl){
		sort(s.begin(),s.end());
		for(cout<<s<<endl;next_permutation(s.begin(),s.end());cout<<s<<endl);
    }
    return 0;
} 


发表于 2016-09-05 13:30:08 回复(5)
//算法思想:全排列的n皇后问题思路,对问题进行递归实现。
//只不过将全排列的数字换为字母进行输出即可。
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=7;//P为当前排列,hashTable记录x是否已经在p中
int n,hashTable[maxn]={false};//当前处理排列的index位
char p[maxn];//储存全排列结果的数组
void generateP(int index,char str[])
{
    if(index==n)//递归边界
    {
        for (int i = 0; i <n; ++i)
        {
            printf("%c", p[i]);//输出当前排列
        }
        printf("\n");
        return;
    }
    for (int x = 0; x <n; ++x)//枚举1~n,试图将x填入p【index】
    {
        if (hashTable[x]==false)//如果x不在p[0]~p[index-1]中
        {
            p[index]=str[x];//令p的index位为先,即把str[x]加入当前排列
            hashTable[x]=true;//记x已经在p中
            generateP(index+1,str);//处理排列的index+1位
            hashTable[x]=false;//已处理完p[index]为x的子问题,还原状态
        }
    }
}
int main(int argc, char const *argv[])
{
    char str[maxn];
    while(scanf("%s",str)!=EOF)
    {
        n=strlen(str);
        sort(str,str+n);//将原始数组进行大小排序
        generateP(0,str);
        printf("\n");
    }
    return 0;
}


发表于 2019-02-05 13:46:10 回复(0)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 7;

char site[maxn] = {0};
string str;

void solve(int num)
{
    if(num == str.length())
    {
        for(int i = 0; i < str.length(); ++i)
        {
            cout << site[i];
        }
        cout << endl;
    }
    else
    {
        int flag = 0;       // 判断是否出现过
        char tmp;
        for(int i = 0; i < str.length(); ++i)
        {
            // 判断是否出现过
            tmp = str[i];
            flag = 0;
            for(int j = 0; j < num; ++j)
            {
                if(site[j] == tmp)
                {
                    flag = 1;
                    break;
                }
            }
            if(flag == 1) continue;
            site[num] = str[i];
            solve(num+1);
        }
    }
}

int main()
{
    
    int count = 0;
    while(cin >> str)
    {
        sort(str.begin(), str.end());       // 按字典序输出
        solve(0);
        cout << endl;
    }

    return 0;
}


发表于 2016-08-04 17:06:58 回复(1)