全排列问题(三个衍生问题 )

1001-高同学

发表文章数:265

首页 » LeetCode » 正文

鄙人不才,遇见的全排列问题和其衍生问题一共三种:1、无重复元素全排列问题。2、有重复元素全排列问题。3、n皇后问题

一、无重复元素全排列问题。给定一个数n,求从1~n的全排列。

看到网上教程很多都在说可以划分为以下几种情况: 以1开头,2~n的全排列;以2开头,1和3~n的全排列;…;n开头,1~n-1的全排列。

这个方法很好理解,但不好想,也不好写。真正理解要建立在对递归真了解的基础之上。不太理解先别着急,我们来总体分析一下(手动滑稽):一个函数,姑且叫它f(n),这个函数里面有一个for循环,当循环里的数满足一定条件的时候,我们进行调用f(n),这样,就是在循环中调用递归函数。当进行f(n)的时候,系统就会调用栈,自动地将当前的数据保存在栈中,当递归返回时,就会执行f(n)的下一条语句。

好了,废话了这么多,也算是把鄙人对着这三个问题的理解写出来了。其实只要这个问题理解了,剩下的有重复元素排列问题和n皇后问题很轻易就能理解代码。但是要注意,重复元素排列在拍之前要确定该数是否在之前出现过,n皇后问题我们用数组下标表示列。

 

代码二:有重复元素排列问题:

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e4+110;
char ch[maxn];
int cnt[maxn] = {0};
int tmp[maxn] = {0};
char num[maxn];
bool nt(int beg,int to)
{
    for(int i=beg; i<to; i++)
    {
        if(ch[i] == ch[to])
            return false;
    }
    return true;
}
void f(int n,int m)
{
    if(n+1 == m)
    {
        for(int i=1; i<=n; i++)
        {
            cout<<num[i];
        }
        cout<<endl;
    }else
    {
        int x;
        for(int i=1; i<=n; i++)
        {
            x = (int)ch[i];
          //  cout<<"x="<<x<<endl;
            if(tmp[x]<cnt[x] && nt(1,i))    //如果出现次数少于等于该元素的个数并且该元素在前面没有出现过
            {
                tmp[x]++;
                num[m] = ch[i];
                f(n,m+1);
                tmp[x]--;
            }
        }
    }
}
int main()
{
    cout<<"请输入元素个数:"<<endl;
    
    int n,x;
    cin>>n;
    cout<<"请输入元素"<<endl;
    for(int i=1; i<=n; i++)
    {
        cin>>ch[i];
        x = (int)ch[i];
        cnt[x]++;
    }
    //对有重复的序列进行排序
    f(n,1);
    return 0;
}

 

 

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《全排列问题(三个衍生问题 )》 发布于2018-10-05

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录