AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 94. 递归&非递归STL实现排列型枚举    原题链接    简单

作者: 作者的头像   秦淮岸灯火阑珊 ,  2019-01-17 20:47:32 ,  所有人可见 ,  阅读 6890


14


11

题目描述

把 $1~n$ 这 $n$ 个整数排成一行后随机打乱顺序,输出所有可能的次序。

输入格式
一个整数$n$。

输出格式
按照从小到大的顺序输出所有方案,每行1个。

首先,同一行相邻两个数用一个空格隔开。

其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。

数据范围
$1 \le n \le 9$
输入样例:

3

输出样例:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

算法1

STL做法(特殊做法)
C++STL中全排列函数next_permutation,详情可以自己百度

正解

(暴力枚举)
首先提一句,代码风格诡异,代码量大,而且巨丑
我的思路大致是这样的,首先呢我们知道,这道题目的输出是按照字典序的,所以呢我们果断选择深度优先搜索
接着来看,我们的循环就不能是之前类似于for(int i=x+1;i<=n;i)了,就必须是for (i=1;i<=n;i0),因为此时我们不再是之前的升序排序输出!
所以说这里必须引用搜索中极为常见的vis数组,也就是判重数组,判断数组,判断这个数字是否被使用过。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,vis[11];
stack<int> p;
void dfs(int x)
{
    if (x==n+1)
    {
        stack<int> q=p,s;
        while(!p.empty())
            s.push(p.top()),p.pop();
        while(!s.empty())
            cout<<s.top()<<" ",s.pop();
        p=q;
        cout<<endl;
        return ;
    }
    for (int i=1;i<=n;i++)
        if (!vis[i])
        {
            vis[i]=1;
            p.push(i);
            dfs(x+1);
            vis[i]=0;
            p.pop();
        }
    return ;
}
int main()
{
    cin>>n;
    dfs(1);
}

正解2

#include <bits/stdc++.h>
using namespace std;
int q[110],n,vis[110];
void dfs(int x)
{
    if (q[0]==n)
    {
        for (int i=1;i<=q[0];i++)
            cout<<q[i]<<" ";
        puts("");
        return ;
    }
    for (int i=1;i<=n;i++)
        if (!vis[i])
        {
            vis[i]=1;
            q[++q[0]]=i;
            dfs(i+1);
            q[q[0]--]=0;
            vis[i]=0;
        }
    return ;
}
int main()
{
    cin>>n;
    dfs(1);
}

正解三 位运算

#include <bits/stdc++.h>
using namespace std;
int q[110],n;
void dfs(int x,int now)
{
    if (q[0]==n)
    {
        for (int i=1;i<=q[0];i++)
            cout<<q[i]<<" ";
        puts("");
        return ;
    }
    for (int i=1;i<=n;i++)
        if (!(now>>(i-1) & 1))
        {
            q[++q[0]]=i;
            dfs(i+1,now+(1<<(i-1)));
            q[q[0]--]=0;
        }
    return ;
}
int main()
{
    cin>>n;
    dfs(1,0);
}

非递归类型枚举.

#include <bits/stdc++.h>
using namespace std;
const int N=11;
int n,a[N];
int main() 
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        a[i]=i;
    do
    {
        for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }while(next_permutation(a+1,a+1+n));
    return 0;
}

22 评论


用户头像
只配吃三碗饭   2022-01-27 15:57         踩      回复

STL写法为什么要加1


用户头像
我什么都不会   2022-01-11 20:55         踩      回复

大佬可以解释一下位运算吗??


用户头像
ssssssqqy   2021-08-07 00:15         踩      回复

大佬为什么第三种的next-permutation要放在最后啊,不能用在前面嘛。

用户头像
ssssssqqy   2021-08-07 00:16         踩      回复

是固定写法吗

用户头像
peterHUAN   2021-11-12 12:39    回复了 ssssssqqy 的评论      2    踩      回复

如果写在前面,就少了最小的那个排列了。


用户头像
markchen   2021-04-19 14:45         踩      回复

第一种解法为什么要用栈呢,用个vector不是更好写呀


用户头像
Takeyourtime   2021-03-03 22:47         踩      回复

大佬们可以帮忙解答一下为什么next_permutation(a+1,a+1+n)这句代码里要加1吗?蒻蒻飘过~~

用户头像
欧拉AC   2021-03-24 11:26         踩      回复

因为i是从1开始的

用户头像
朴小明   2021-07-09 20:32         踩      回复

stl的函数经常是左闭右开的


用户头像
爱妃   2021-01-19 23:25         踩      回复

太强了!!!


用户头像
TDDA@EliPsE   2021-01-19 18:21         踩      回复

这三个版本实质并没有改变啊,只是写法不一样啊,求问,不同写法的优点和缺点。个人觉得第一给永栈写的太冗长了。


用户头像
Leonardo   2020-04-05 10:24         踩      回复

大佬 位运算版本dfs函数的x参数没看出是什么用途?能解答一下吗

用户头像
coffeenet   2020-05-18 18:14         踩      回复

同想知道!

用户头像
垫底抽风   2020-08-28 10:07         踩      回复

可能是秦巨佬在写完第一个版本之后直接改的,忘了把那个 x 去掉了2333

用户头像
秦淮岸灯火阑珊   2020-08-29 08:50    回复了 垫底抽风 的评论         踩      回复

抽风好懂我啊。。。。。问题是我不巨啊


用户头像
张小白   2019-07-31 09:49         踩      回复

dalao法三能发布一个非递归版本吗,弱鸡想看一下qaq

用户头像
秦淮岸灯火阑珊   2019-07-31 10:18         踩      回复

好滴,晚上制作一份.

用户头像
张小白   2019-07-31 15:21    回复了 秦淮岸灯火阑珊 的评论         踩      回复

多谢dalao

用户头像
秦淮岸灯火阑珊   2019-08-01 07:21    回复了 张小白 的评论         踩      回复

已经加入了,昨天晚上头痛,休息去了.非常抱歉啊.

用户头像
张小白   2019-08-01 15:35    回复了 秦淮岸灯火阑珊 的评论         踩      回复

大佬辛苦了,其实弱鸡想看一下这题回溯的非递归写法qaq

用户头像
秦淮岸灯火阑珊   2019-08-01 17:47    回复了 张小白 的评论         踩      回复

那我晚上打一份.

用户头像
张小白   2019-08-01 20:28    回复了 秦淮岸灯火阑珊 的评论         踩      回复

阿里嘎多


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息