数字全排列_牛客博客

题意；
从1～9之间顺序取N个数字，组成每位数不重复的所有可能的N位数，按从小到大的顺序进行编号，当输入其中的任何一个数M是，能找出该数对应的编号。如：当N ＝ 3，M = 132时，则输出： [123(1), 132(2), 213(3), 231(4), 312(5), 321(6)]——> X = 2

Input
输入只有一行，两个正整数N和M(1 ≤ N ≤ 9，1 ≤ K ≤ 987654321)，之间用一个空格分隔开。

Output
输出对应的编号X。
Sample Input
3 132
Sample Output
2

这类题其实就是让我们来对数的全排列

首先简单的说一下思路：例如数字 3142 他前面一定有1和2 开头之后剩下三个数的全排列也就是阶乘；所以一定会用到阶乘不妨就写一个阶乘函数，当然这个阶乘函数引入的不是这个位的位数而是这个位数-1的阶乘。这一点应该很好理解。之后就来研究该怎么处理这个阶乘。 3的话，在它之前一定有1,2的全排也就是阶乘乘以二。

中间一点错误：一开始我是用这个数减一后来考虑到后面就不对了 1先跳过，看4 他要是按这种方法的话就是3种可是他跟最后一位最多2个数字就2种情况：42 ， 24 ；

正确思路：找到逆序数也就是比他位数低，而且数值也比这位数小像 3142 一样就是2*(3!)*0*(2!)*1*(1)=13;

# include<stdio.h>
int solve(int num)
{
    int sign=1,i;
    for(i=1;i<=num;i++)
        sign*=i;
    return sign;
}
int main()
{
    char str[20];
    int n,sum=0,count=0,i,j;
    scanf("%d %s",&n,str);
    for(i=0;i<n-1;i++)
    {
        count=0;
        for(j=i+1;j<n;j++)
            if(str[j]<str[i])count++;//计算逆序数
        sum+=count*solve(n-i-1);//后面可能出现的情况计算
    }
    printf("%d\n",sum+1);
    return 0;
    
}

方法二： <mark>深搜</mark>

深搜这种方法也不用大说直接看代码吧。

#include<stdio.h>//深度搜索
# include<string.h>
int n,loop,vis[100],j,result[100],Count,sign;
char str[100];
void DFS(int step)
{
    int i;
    sign=0;
    if(step==n+1)//结束
    {
        Count+=1;
        for(i=1;i<=n;i++)
        {
            if(result[i]==str[i-1]-'0')//判断找得这个数是不是需要的那个数
                sign+=1;
        }
        if(sign==n)//是这个数
        loop=Count;//这就是那个数排序后的序号
        return;
    }
    for(i=1;i<=n;i++)//从一看是dfs
    {
        if(!vis[i])
        {
            vis[i]=1;//标记这个数用过避免重复使用
            result[step]=i;
            DFS(step+1);
            vis[i]=0;//还原
        }
    }
}
int main()
{
    scanf("%d %s",&n,str);
    memset(vis,0,sizeof(vis));
    Count=0;
    sign=0;
    DFS(1);//从一开始dfs
    printf("%d\n",loop);
    return 0;
}

方法三：

这种方法其实是中用c++中的一种函数next_permutation和prev_permutation 现在还没大搞懂 ```cpp //第一种方法在algorithm里面有个next_permutation可以实现，排序道理是一样的 //如果把next_permutation换成prev_permutation,一开始赋值就应是倒序,如:321 # include # include # include using namespace std; int main() { int num,count=0,i; char str[20],s[20]; cin>>num>>str; for(i=0;i

//换位的递归思想还不错，就是没按字典顺序来，仅供看思想
# include<iostream>
using namespace std;
char str[20];
int t,leap;
void Swap(int *a,int *b)//重视
{
  int temp;
   temp=*a;
    *a=*b;
    *b=temp;
}
void Array(int *s,int Count,int n)
{
    if(leap)return;
    if(Count==n)
    {
        t++;
        int sign=0;
        for(int i=0;i<=n;i++)
        if(s[i]==str[i]-'0')sign++;
        if(sign==n+1)
        {
            cout<<t<<endl;
            leap=1;
        }
        return;
    }
    for(int i=Count;i<=n;i++)
    {
    
        Swap(&s[i],&s[Count]);
        Array(s,Count+1,n);
        Swap(&s[i],&s[Count]); 
    }

}
int main()
{
    int s[20];
    int num,i;
    while(cin>>num>>str)
    {
    t=0;
    leap=0;
    for(i=0;i<num;i++)
        s[i]=i+1;
    Array(s,0,num-1);
    }
    return 0;
}

<mark>总结</mark> ；

遇到这类题往枚举，深搜上想好点，毕竟时间复杂度太大
最大8^8 这种好想点，再者就是找先规律。当然也不要每个题都能找得到规律，功夫不到家就是白忙活，所以，Fighting！！！