全排列

[编程题]全排列

热度指数：331 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

输入正整数N，输出由1到N这N个数(N<=7)的所有排列，每行一个排列，数与数之间有一个空格，两个排列中，第一个数小的优先输出，第一个数相同，比较第二个数，后面以此类推。

输入描述:

一个正整数N

输出描述:

所有排列

示例1

输入

输出

算法知识视频讲解

PopcornZQ

有现成的函数，不过也要理解手撕的思路。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n,c=0;
    cin >> n;
    vector<int>zq(n);
    for (auto &i : zq)
        i = ++c;
    do {
        for (auto &i : zq)
            cout << i << " ";
        cout << endl;
    }
    while(next_permutation(zq.begin(), zq.end()));//当前序列不存在下一个排列时，函数返回false，否则返回true.所以要用do while
    return 0;
}

思路：

#include<iostream>
#include <string>
using namespace std;
int a[10], book[10], n;//C语言的全局变量没赋值之前都是0
void dfs(int step)//step表示站在第几个盒子前
{
    if (step == n + 1)//如果站在第n+1个盒子前，表示前n个盒子已经放好扑克牌
    {
        for (int i = 1; i <= n; ++i)
            cout << a[i]<<" ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; ++i)//一共n张牌
    {
        if (book[i] == 0)//表示i号扑克牌还在手上
        {
            a[step] = i;//将i号扑克牌放入到第step个盒子中
            book[i] = 1;//表示i号牌已经放了，不在手上
            dfs(step+1);//第step个盒子已经放好扑克牌，接下来要走到下一个盒子
            book[i] = 0;//将牌收回，进行下一次尝试
        }
    }
    return;
}
int  main()
{
    cin >> n;
    dfs(1);//首先站在1号盒子前，
    return 0;
}

编辑于 2019-08-18 20:17:50 回复(0)

C/C++

鱼香-肉丝

#include<bits/stdc++.h>
using namespace std;
bool mark[10];
int ans[10];
int n;
void DFS(int num)
{
    if(num==n+1)
    {
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(mark[i]==false)
        {
            mark[i]=true;
            ans[num]=i;
            DFS(num+1);
            mark[i]=false;
        }
    }
    return ;
}
int main()
{
    cin>>n;
        for(int i=1;i<=n;i++) mark[i]=false;
        //mark[1]=true;
        DFS(1);
    return 0;
}

递归的应用-回溯法
但是我不是很明白的地方是，有的时候DFS函数中判断num==n+1，从i=1遍历，ans[num]=i，主函数中不用mark[1]=true；
但有时判断num==n，从i=2遍历，ans[num+1]=i，主函数需要写mark[1]=true。而且两中方法得出的结果不一样，请问有谁知道这怎么解释吗？回溯法我不是很懂。