Sort elements using specifc order in python

Question

Sort all the strings lexicographically but if a string is present completely as a prefix in another string, then string with longer length should come first.

e.g. 1 test, testtube are 2 strings and the string test is present as a prefix in testtube

sorted- testtube, test.

e.g. 2 bank, ant, testtube, test

sorted- ant, bank, testtube, test

How can we do this in python ? Tried alot but have'nt got any solution, need help.

Answer 1

Perhaps append an "impossibly large" character at the end of each string?

def sort(a):
   return sorted(a, key=lambda s: s + chr(0x10FFFF))

Demo:

>>> sort(['test', 'testtube'])
['testtube', 'test']

>>> sort(['bank', 'ant', 'testtube', 'test'])
['ant', 'bank', 'testtube', 'test']

>>> sort(['test', 'testbb', 'testa'])
['testa', 'testbb', 'test']

It's the largest code point (chr even gives a ValueError for something larger) and actually a "noncharacter" and shouldn't occur naturally but we're free to use it for this:

Noncharacters are code points that are permanently reserved in the Unicode Standard for internal use. They are not recommended for use in open interchange of Unicode text data. [...] Applications are free to use any of these noncharacter code points internally.

Later in that section, the standard even suggests this usage (emphasis mine):

[...] U+10FFFF is associated with the largest legal UTF-32 32-bit code unit value, 10FFFF₁₆. This attribute renders these two noncharacter code points useful for internal purposes as sentinels. For example, they might be used to indicate the end of a list, to represent a value in an index guaranteed to be higher than any valid character value, and so on.

Answer 2

Python comes with a sort built in, accessible through list.sort or the sorted function, and the key argument lets you configure the order to sort by. The key function will be called on each element of the input, and the key function's return values will be compared instead of the original input elements to determine ordering.

By default, string comparison considers "end of string" to be lower than an actual character. With the order you want, "end of string" is considered higher than an actual character. We can represent this by making a list of characters from a string, and adding a special "end of string" marker to the end of the list. Our "end of string" marker implements comparison such that "end of string" compares equal to another "end of string", but greater than any character:

from functools import total_ordering

@total_ordering
class EndMarker(object):
    def __eq__(self, other):
        # Only equal to another end-marker...
        if not isinstance(other, EndMarker):
            return NotImplemented
        return True
    def __lt__(self, other):
        # and not less than anything.
        return False

endmarker = EndMarker()

def funky_sort(strings):
    return sorted(strings, key=lambda string: list(string) + [endmarker])

Alternatively, we can rely on the limited range of Unicode code points, by converting each character in the strings to its numerical code point, and making the end marker an integer greater than any possible code point. Or, we could make the end marker a floating-point infinity:

endmarker = float('inf')

def funky_sort(strings):
    return sorted(strings, key=lambda string: [ord(char) for char in string] + [endmarker])