Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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;
}
share|improve this answer
    
thanks very much. There is no duplicated character in the string. I'm sorry for not making it clear. –  FihopZz Nov 1 '12 at 3:50
    
Excellent! I took that section out then. –  Danny Kirchmeier Nov 1 '12 at 3:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.