Lexicographical sorting

Question

I'm doing a problem that says "concatenate the words to generate the lexicographically lowest possible string." from a competition.

Take for example this string: jibw ji jp bw jibw

The actual output turns out to be: bw jibw jibw ji jp

When I do sorting on this, I get: bw ji jibw jibw jp.

Does this mean that this is not sorting? If it is sorting, does "lexicographic" sorting take into consideration pushing the shorter strings to the back or something?

I've been doing some reading on lexigographical order and I don't see any point or scenarios on which this is used, do you have any?

Answer 1

It seems that what you're looking for is a better understanding of the question, so let me just make it clear. The usual sorting on strings is lexicographic sorting. If you sort the strings [jibw, ji, jp, bw, jibw] into lexicographic order, the sorted sequence is [bw, ji, jibw, jibw, jp], which is what you got. So your problem is not with understanding the word "lexicographic"; you already understand it correctly.

Your problem is that you're misreading the question. The question doesn't ask you to sort the strings in lexicographic order. (If it did, the answer you got by sorting would be correct.) Instead, it asks you to produce one string, got by concatenating the input strings in some order (i.e., making one string without spaces), so that the resulting single string is lexicographically minimal.

To illustrate the difference, consider the string you get by concatenating the sorted sequence, and the answer string:

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

Now when you compare these two strings — note that you're just comparing two 14-character strings, not two sequences of strings — you can see that the correct answer is indeed lexicographically smaller than your answer: your answer starts with "bwjij", while the correct answer starts with "bwjib", and "bwjib" comes before "bwjij" in lexicographic order.

Hope you understand the question now. It is not a sorting question at all. (That is, it is not a problem of sorting the input strings. You could do sorting on all possible strings got by permuting and concatenating the input strings; this is one way of solving the problem if the number of input strings is small.)

Answer 2

You can convert this into a trivial sorting problem by comparing word1 + word2 against word2 + word1. In Python:

def cmp_concetanate(word1, word2):
    c1 = word1 + word2
    c2 = word2 + word1
    if c1 < c2:
        return -1
    elif c1 > c2:
        return 1
    else:
        return 0

Using this comparison function with the standard sort solves the problem.

Answer 3

I've been using F# in this Facebook hacker cup. Learned quite a bit in this competition. Since the documentation on F# on the web is still rare, I think I might as well share a bit here.

This problem requests you to sort a list of strings based on a customized comparison method. Here is my code snippet in F#.

    let comparer (string1:string) (string2:string) =
         String.Compare(string1 + string2, string2 + string1)

    // Assume words is an array of strings that you read from the input
    // Do inplace sorting there
    Array.sortInPlaceWith comparer words
    // result contains the string for output
    let result = Array.fold (+) "" words