Q 1815: [2014 5th exam questions]Ranking order

Time limit: 1Sec Memory Limit: 128MB

Title Description

If a string is formed with the 4 letters a b c d, there are 4!=24 kinds, and if they are put in order, each string corresponds to a serial number:: abcd 0 abdc 1 acbd 2 acdb 3 adbc 4 adcb 5 bacd 6 badc 7 bcad 8 bcda 9 bdac 10 bdca 11 cabd 12 cadb 13 cbad 14 cbda 15 cdab 16 cdba 17 … Now there are no more than 10 two different lowercase letters and given the string they form, can you find the serial number of the string in all the arrangements?

Input

One row, one string.

Output

A line, an integer, indicating the serial number of the string among all the strings generated by all permutations of its letters. Note: the smallest ordinal number is 0.

Sample Input

1

bdca

Sample Output

1

11

C Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


#include<stdio.h>
#include<string.h>
char s[11],p[11],d[11],c;        //p is used to store the s-array (invariant) d is used to record the s-array (variable) 
int cd,num=0,b[11];              //b is used to mark; cd records the length of the array; num counts 
void dfs(int x)
{
    int i,j;
    if(x==cd)                    //If the length of x is the same as the length of cd num++ 
    {
        num++;
        if(strcmp(p,d)==0)       //If the current array is the same as the s array, output (num-1) because abcd is 1 
    {
        printf("%d",num-1);
    }
        return ;
    }
    for(i=0;i<cd;i++)
    {
        if(!b[i])
        {
            d[x]=s[i];            //Record 
            b[i]=1;               //Marker 
            dfs(x+1);             //dfs 
            b[i]=0;               //Retrospective 
        }
    }
}
int main()
{
    int i,j,n=0;
    scanf("%s",s);                    //Input 
    strcpy(p,s);                      //Copy to p-array 
    cd=strlen(s);                     //Record length 
     for(i=0;i<strlen(s)-1;i++)       //bubble sort 
     {
         for(j=0;j<strlen(s)-1-i;j++)
         {
             if(s[j]>s[j+1])
             {
                 c=s[j];
                 s[j]=s[j+1];
                 s[j+1]=c;
             }
         }
     }
     memset(b,0,sizeof(b));            //Set b to zero Set the beginning to zero as well
     dfs(0);                           //dfs 
    return 0;
 }