@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.
