How to sort string rotations without using a matrix

I want to sort the rotations of a string.

For example:

For S = 'abaeb', a rotati开发者_JAVA技巧on could be 'baeba'

I need to obtain a list of indexes to S, sorted in lexicographical order.

In our example: V = 02413.

The answer must exclude the trivial matrix rows sort.

Edited: after pointed by Justin Peel

Just append the string to itself bbaeb becomes bbaebbbaeb(a handy trick for problems involving rotation of string).
Find suffix array.
Traverse it and only select the values less than the length of orignal string(5) . Suffix array for above string

aeb  7
aebbbaeb  2
b  9
baeb  6
baebbbaeb 1
bbaeb 5
bbaebbbaeb 0
eb  8
ebbbaeb  3

S = 7 2 7 6 1 5 0 4 8 3

Now aftertraversing Ans= 2 1 0 4 3

Edit over

You can solve it in O(n) time complexity with the use of Suffix array. Basically suffix array for a string contains index of all suffix of a string in lexicographic order.
For string abaeb, the suffix in lexicographic order are:

abaeb (0)
aeb   (2)
b     (4) 
baeb  (1)
e     (3)

So the suffix array S=02413

Code with O(n log^2n) time complexity is given at that link with detailed explanation and next page have optimization for O(n). If you want to keep your code simple then using a comparison operator as already answered is the key. And if your of main concern is efficiency then use o(n) suffix array construction.

Generally, for sorting, you don't need to keep all the sorted items in memory in parallel, you need just to be able to compare any pair of them.

What i mean, you can sort indexes of string rotation beginning (i.e. 1 = 'baeba', etc) and provide a comparison method which will compare the rotations based on that index.

While the complexity is not better than nLog(n), the code should be very simple. Also, memory complexion is close to the best u can get. Somehow exploiting the knowledge that the sorted items are not random, might probably give you better complexity (but i currently have no idea how to do it).

If I understand correctly, you have an input string, and you are considering all rotations. For example the N rotations of an N-length string would be, e.g.:

rotations("abcd") -> ["abcd"*, "dabc", "cdab", "bcda"]

You wish to write a comparator function, compare(rotation1, rotation2), which will say whether rotation1 is < or > or == rotation2, in the context that the *original rotation was abcd, or alternatively, have a function key(rotation) which is equivalent to the above comparator function.

If this is incorrect, please clarify the question. =) If it is correct, your answer is as follows:

original = 'abcd'

letterPositions = defaultdict(set)
for i,letter in enumerate(original):
    letterPositions[letter].add(i)

def numIndicesRotated(rotated):
    possibilities = set(range(len(original)))
    for i,letter in enumerate(rotated):
        possibilities &= {(j-i)%len(original) for j in letterPositions[letter]}
        if len(possibilities)==1: #optimization
            break                 #optimization

    if len(possibilities)==1:
        return possibilities.pop()
    else:
        raise Exception('not a rotation')

Note that rotations may not be cleanly unorderable if you have a string which has rotations that are itself, e.g. abcabc.

Then you can do something like sorted(myRotations, key=numIndicesRotated)