首页 > 其他分享 >P1706 全排列问题(DFS)

P1706 全排列问题(DFS)

时间:2022-10-26 20:45:48浏览次数:40  
标签:输出 排列 数字 int DFS 重复 P1706 序列

全排列问题

题目描述

按照字典序输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数n

输出格式

由1 ~ n组成的所有不重复的数字序列,每行一个序列。

每个数字保留5个场宽。

样例输入

3

样例输出

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

思路

深搜,记录每个数的状态和当前是第多少个数,每完成一组就进行回溯,可以保证是按字典序输出且不重复

#include<bits/stdc++.h>
using namespace std;
int n;
int p[10];
int ans[10];

void print()
{
    for(int i = 0; i < n; i++){
        printf("%5d", ans[i]);
    }
    printf("\n");
}

void dfs(int now)
{
    if(now == n){
        print();
    }
    for(int i = 1; i <= n; i++){
        if(!p[i]){
            ans[now] = i;
            p[i] = 1;
            dfs(now + 1);
            p[i] = 0;
        }
    }
}

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

标签:输出,排列,数字,int,DFS,重复,P1706,序列
From: https://www.cnblogs.com/14Si/p/16829949.html

相关文章

  • DFS--同一个方向找出所有子字符串的个数
     字符迷阵是一种经典的智力游戏。玩家需要在给定的矩形的字符迷阵中寻找特定的单词。在这题的规则中,单词是如下规定的:1.在字符迷阵中选取一个字符作为单词的开头;2.选取......
  • DFS(全排列)--相同序号不能相邻
     小多想在美化一下自己的庄园。他的庄园毗邻一条小河,他希望在河边种一排树,共M棵。小多采购了N个品种的树,每个品种的数量是Ai(树的总数量恰好为M)。但是他希望任意......
  • DFS--输出下一个数字
    题目描述JamJam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数,而是使用小写英文字母计数,他觉得这样做,会使世界更加丰富多彩。在他的计数法中,每个数字的位数都是相同的......
  • STL函数之全排列next_permutation
    题目描述牛牛的作业薄上有一个长度为n的排列A,这个排列包含了从1到n的n个数,但是因为一些原因,其中有一些位置(不超过10个)看不清了,但是牛牛记得这个数列顺序对的数量是k,顺......
  • DFS(全排列)--和大于乘机的方案数
    题目描述一个袋子里面有n个球,每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。例如:如果袋子里......
  • [Oracle] LeetCode 694 Number of Distinct Islands 标记路线的DFS
    Youaregivenanmxnbinarymatrixgrid.Anislandisagroupof1's(representingland)connected4-directionally(horizontalorvertical.)Youmayassumea......
  • AcWing 271杨老师的照相排列
    思路\(1=<k<=5\),所以最多会有五个位置,五个位置分配人,即集合为f[a][b][c][d][e]表示五个位置各放了a,b,c,d,e个人的方法的数量,同时h[1]>=h[2]>=h[3]>=h[4]>=h[5],所......
  • ACWing - 4493 -- 思维题&&并查集&&dfs
    题目描述环形连通分量思路对于一个无向图中的简单环(环中边的数量等于点的数量),有一个很强的性质:每个点的度数等于\(2\)。那么我们只需要先找出所有的连通块,然后判......
  • 使用PdfSharp从模板生成Pdf文件
    ​最近在做一个生成文档的需求。通过先制作一个包含各字段占位符的文档模板,导入这个模板并填写内容替换掉占位符,再输出成最终文件。由于版式固定,安全性更好,业务上常用Pdf......
  • BZOJ 2111([ZJOI2010]Perm 排列计数-乘法逆元+完全二叉树模型+数列分数表示法)
    2111:[ZJOI2010]Perm排列计数TimeLimit: 10Sec  MemoryLimit: 259MBSubmit: 478  Solved: 283[​​Submit​​][​​Status​​][​​Discuss​​]......