you're a little off here. Using your definition of n, there are n! strings in the sorted array. Finding a particular one using binary search takes O(log n!) time.

public static int IndexOfPermutationInLexicographicOrder(string start, string prefix, int index) { if (prefix == start) return index; int i = Array.BinarySearch(start.ToCharArray(), prefix[0]); index += i * Factorial(prefix.Length - 1); index = IndexOfPermutationInLexicographicOrder(start.Remove(i, 1), prefix.Remove(0, 1), index); return index; }

Just to clarify, initial call to the function will be made as follows IndexOfPermutationInLexicographicOrder("abcd", "bcad", 0), if bcad is the string whose index you need to find. the "start" specifies the original sort order/lexical order

How about this: We look for the first "out of position" character, c, in our permutation string. Suppose we find it at "i". We know there must have been at least ret=(c-i)*(N-i-1) permutations before it. But there could be more than that, since the final part (i to N) might also contain some out-of-order characters. The "index" of this final part permutation must then be added to ret. We can easily find this index recursively using the logic above, if we first map that final part to a corresponding permutation. This can be easily done as per the code below. The total runtime of this method is O(N), where N is the length of the permutation. public static long getPermIndex(String perm) { int ret=0; for(int i=0;i

Here's a solution that is O(k) where k is the number of letters in the input string For example: Say you have 6 letters being permuted (abcdef) and you want to know the index of the particular permutation, say facbed sort the letters: abcdef take the first letter of the input 'f' find its index in the sorted letters (5) Now you know that its index will be in the range of 5 * (n-1)! - compute that value: 5 * 120 = 600 now remove that letter from the input and sort the remainder abcde take the second letter of the input 'a', note its position is 0, so compute 0 * (n-2)! = 0 remove that letter and sort the rest bcde next letter of input is 'c', which is at position 1, so compute 1 * (n-3)! = 6 remove the letter, sort the rest, you get 'bde' and so on def findLexiPerm( input, sorted ): letters = input.split() n = len(input) first = input[0,1] index = sorted.find(first) * (n-1)! return index + findLexiPerm(str(letters[1:n]),sorted[1:n]) input = 'facbed' sorted = input.split().sort() index = findLexiPerm(input,sorted) Untested pythonish pseudocode but I believe this is the right answer

This is equivalent to searching in sorted array (which means that the word 'permutation' is here just to mislead you), that is, binary search. Complexity is O(log n) By the way, linear scan in an array of all permutations of n-character string is O(n!)

Here's my solution in Java, which takes log(N) time to 'calculate' the position. N being the length of the permutation string. Using a binary search ignores the fact that the list is not sorted but also complete, so we can calculate the position without going through the list. public static int getPermIndex(String[] perms, String needle) { // perms[0] is ordered letters, take it as reference int itemsBefore = 0; for (int i = 0; i 0) itemsBefore += diff * fact(needle.length() - (i + 1)); } return itemsBefore; } public static int fact(int n) { if (n == 0 || n == 1) return 1; return n * fact(n - 1); }

Your code is not correct, for this String[] s = {"123","132","213","231","312","321"}; for 321 will return 4 instead of 5.