Here is a constant time formula, LetterRankInSortedString is index of
alphabate if all characters in string are sorted lexographically starting
from 1.
Index = 0;
For(i=0; i < LengthOfString; i++)
{
Letter = string[i];
Index + = (LetterRankInSortedString(Letter) - 1) *
(TotalPermutationsPossible/ (LengthOfString-i));
}
On Mon, May 28, 2012 at 12:26 AM, saurabh agrawal <saurabh...@gmail.com>wrote:
> @atul:
> i dont agree that "baa" should come once or twice is arguable.
> It definitely have to be one time only..
> we are supposed to get all lexicographic combinations (which implicitly
> means no two strings will be same..)
>
> On Mon, May 28, 2012 at 12:23 AM, atul anand <atul.87fri...@gmail.com>wrote:
>
>> @saurabh : i kinda assumed that string will not contain
>> repeated character. reason being if string has repeated character , say in
>> your case "baa" then baa will be repeated
>> twice ....hence it would be difficult to justify the output for this
>> input answer could be say 2 or 3 or both are correct.
>>
>> On Mon, May 28, 2012 at 12:16 AM, saurabh agrawal
>> <saurabh...@gmail.com>wrote:
>>
>>> @atul:
>>> if i have understood ..
>>> ur solution will break when the string has repeated characters.
>>>
>>> e.g. for "baa"
>>>
>>> On Tue, May 22, 2012 at 3:43 PM, partha sarathi Mohanty <
>>> partha.mohanty2...@gmail.com> wrote:
>>>
>>>> sorry it was treeset.... Here is the code..
>>>>
>>>> public class asd1 {
>>>>
>>>>
>>>> public static TreeSet<String> t = new TreeSet<String>();
>>>> public static int j = 0;
>>>> public static void main(String args[]) {
>>>>
>>>>
>>>>
>>>>
>>>> String s= "edcba";
>>>> permute("", s);
>>>> System.out.println(t.toString());
>>>> int length=t.size();
>>>> String[] arr=(String[]) t.toArray(new String[length]);
>>>> for(int i =0;i<length;i++)
>>>> {
>>>> System.out.println(arr[i]);
>>>> if(arr[i].equals(s)){
>>>> System.out.println(i+1);
>>>> break;
>>>> }
>>>> }
>>>> }
>>>>
>>>> public static void permute(String st, String chars) {
>>>> if (chars.length() <= 1)
>>>> t.add(st+chars);
>>>> else
>>>> for (int i = 0; i < chars.length(); i++) {
>>>> try {
>>>> String newString = chars.substring(0, i)
>>>> + chars.substring(i +
>>>> 1);
>>>> permute(st + chars.charAt(i),
>>>> newString);
>>>> } catch (Exception e) {
>>>> e.printStackTrace();
>>>> }
>>>> }
>>>>
>>>> }
>>>> }
>>>>
>>>> On Tue, May 22, 2012 at 2:19 PM, partha sarathi Mohanty <
>>>> partha.mohanty2...@gmail.com> wrote:
>>>>
>>>>> Java has something call treeMap. it stores strings lexographically.. u
>>>>> can always do permutations and store them in a treeMap. and get the rank
>>>>> then... just the idea.. will post the solution once i am done.. what do u
>>>>> guys think.abt the idea???
>>>>>
>>>>>
>>>>> On Tue, May 22, 2012 at 9:46 AM, atul anand
>>>>> <atul.87fri...@gmail.com>wrote:
>>>>>
>>>>>> 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.
>>>>>>
>>>>>
>>>>>
>>>> --
>>>> 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.
>>>
>>
>> --
>> 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.
>
--
Regards,
Rahul Patil
--
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.
