actually we can think of above approach as follows :-
input : cabd
sort(input) = abcd
find first element of the input i.e 'c' in the sorted form i.e abcd
'c' is at found_index=3 ( index starting from 1 )
so permutaion stating from 'c' will come after temp_rank=(found_index -
start_index) * (total_lentgh - 1) !
now after temp_rank we know that permutation starting with 'c' will come.
so to find out the exact index sort(input-1) i.e removing 1st character
('c') from the input(cadb) we will get abd
now permute string "abd" and compare with input - 1 character i.e (abd).
and keep inc the counter , if match is found then you have to add this
counter to temp_rank.
so for the input = cabd
temp_rank = (3 - 1) * (4-1) !
= 2 * 3!
= 12
counter found c = 1;
rank = 12 + c = 13
but i dont think this would be good solution as be have to permute string
and then compare at last...yes we did some optimization.
i was wondering if instead of permuting at the end , we can calculate
minimum number of swaps required to convert input - 1 to sorted input -1
(removing 1st character )using edit distance ...will this work?? .....
On Mon, May 21, 2012 at 11:33 PM, atul anand <atul.87fri...@gmail.com>wrote:
> consider string input = cabd
> now sort this string = abcd
>
> now search 1st character from original string(cabd) in sorted string
> abcd... index found = 3 (index starting from 1 )
>
> now you can arrange left elements from found index i.e index-1 elements in
> (index-1) ! and right elements from found index in (lastIndex - index)!
> before character 'c' occurs at index 0. similarly find for other characters
> and at the end subtract it from n! (n = length of the string ) to find rank
>
>
> On Mon, May 21, 2012 at 11:02 PM, rahul venkat <rahul911...@gmail.com>wrote:
>
>> Given a string. Tell its rank among all its permutations sorted
>> lexicographically.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
