Lexicographic rank of a string

Question

Given a string, find its rank among all its permutations sorted lexicographically. For example, rank of "abc" is 1, rank of "acb" is 2, and rank of "cba" is 6. Assuming there is no duplicated character.

The following is my code:

#include <iostream>
using namespace std;
// A utility function to find factorial of n
int factorial(int i)
{
 if(i == 0)
 return 1;
 return i*factorial(i-1);
}
// A utility function to count smaller characters
// starting from index of ind
int count_smaller_than_cur(string& s, int ind)
{
 int count = 0;
 for(int i = ind+1; i < s.size(); ++i)
 if(s[i] < s[ind])
 count++;
 return count;
}
// A function to find rank of a string in all permutations
// of characters
int rank(string& s)
{
 int r=1;
 int len = s.size();
 int f = factorial(len);
 for(int i=0; i < len; ++i)
 {
 f /= (len-i);
 // count number of chars smaller than str[i]
 // fron str[i+1] to str[len-1]
 int t = count_smaller_than_cur(s, i);
 r += t*f;
 }
 return r;
}
int main()
{
 string str("string");
 cout << rank(str) << endl;
 system("pause");
 return 0;
}

Can anyone help me check it?

Answer 1

I have a couple of issues with the main function.

First, system("pause") may work for windows but won't elsewhere. You should dump it.

Second, Too many returns at the end.

Third, The hardcoded input makes it kinda hard to test (and doesn't look good). Just read the first parameter from the command line or read in from standard in. Here is an easy way to do so:

int main(int argc, char** argv) {
 string str;
 if(argc >= 2){
 str = argv[1];
 } else {
 cout << "Enter a string: ";
 cin >> str;
 }
 cout << rank(str) << endl;
 return 0;
}

• Fihop: thanks very much. There is no duplicated character in the string. I'm sorry for not making it clear.
• Danny Kirchmeier: Excellent! I took that section out then.