Сортировать элементы, используя заданный порядок c в python

Question

Сортировать все строки лексикографически, но если строка присутствует полностью как префикс в другой строке, то строка с более длинной длиной должна стоять на первом месте.

например, 1 test, testtube - 2 строки и тест строки присутствуют в качестве префикса в testtube

sorted- testtube, test.

например, 2 bank, ant, testtube, test

sorted- ant, bank, testtube, test

Как мы можем сделать это в python? Пробовал много, но не нашел решения, нужна помощь.

Answer 1

Возможно добавить «невероятно большой» символ в конце каждой строки?

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

Демонстрация:

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

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

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

Это самая большая кодовая точка (chr даже дает ValueError для чего-то большего) и фактически " noncharacter " и не должно встречаться естественным образом, но мы можем использовать его для этого:

Noncharacters - это кодовые точки, которые постоянно зарезервированы в стандарте Unicode для внутреннего использования. Они не рекомендуются для использования в открытом обмене текстовыми данными Unicode. [...] Приложения могут свободно использовать любые из этих нехарактерных кодовых точек для внутреннего использования.

Позже в этом разделе стандарт даже предлагает такое использование (выделено мое):

[...] U + 10FFFF связано с наибольшим допустимым значением 32-битной кодовой единицы UTF-32, 10FFFF ₁₆ . Этот атрибут делает эти две нехарактерные кодовые точки полезными для внутренних целей в качестве часовых. Например, они могут использоваться для указания конца списка, чтобы представляло значение в индексе, которое гарантированно было больше, чем любое допустимое значение символа и т. Д.

Answer 2

Python поставляется со встроенной сортировкой, доступной через list.sort или через функцию sorted, а аргумент key позволяет настроить порядок сортировки. Ключевая функция будет вызываться для каждого элемента ввода, и возвращаемые значения ключевой функции будут сравниваться вместо исходных элементов ввода для определения порядка.

По умолчанию при сравнении строк "конец строки" рассматривается как быть ниже, чем фактический персонаж. В указанном порядке «конец строки» считается выше, чем фактический символ. Мы можем представить это, составив список символов из строки и добавив специальный маркер «конца строки» в конец списка. Наш маркер «конец строки» реализует сравнение так, что «конец строки» сравнивается равным другому «концу строки», но больше любого символа:

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])

В качестве альтернативы, мы можем положиться на ограниченный диапазон кодовых точек Юникода, путем преобразования каждого символа в строках в его числовую кодовую точку и превращения конечного маркера в целое число, превышающее любую возможную кодовую точку. Или мы можем сделать маркер конца бесконечностью с плавающей точкой:

endmarker = float('inf')

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

Answer 3

Один потенциальный подход, который кажется интуитивно понятным: сначала отсортируйте все как обычно, а затем создайте группы или цепочки, в которых элементы являются идеальным префиксом слева направо. Используя groupby, мы можем решить эту проблему следующим образом.

from itertools import groupby
from operator import itemgetter

def weird_sorting(list_):
    """designed to sort lexically, except when
    a string is a complete prefix of another, in which case
    the order is reversed
    """
    # sort everything lexically
    temp = sorted(list_)
    # get a grouper that indicates 
    # True if current string starts with the previous string
    grouper = [False] + [r.startswith(l) for l, r in zip(temp, temp[1:])]

    output = []
    # Group items in the grouper key, 
    # and reverse all items that have a True group, making sure to 
    # handle the "very first" string that is starting a True chain
    for k, group in groupby(zip(grouper, temp), key=itemgetter(0)):
        items = [v for k, v in group]
        if k:
            prev_item = output.pop()
            reversed_list = [prev_item, *items][::-1]
            output.extend(reversed_list)
        else:
            output.extend(items)
    return output


test1 = ['test', 'testtube']
print(weird_sorting(test1))
test2 = ['bank', 'ant', 'testtube', 'test']
print(weird_sorting(test2))
test3 = ['bank', 'ant', 'testtube', 'test', 'testtubebabies', 'zeta1', 'zeta11', 'zz']
print(weird_sorting(test3))

Выходы:

['testtube', 'test']
['ant', 'bank', 'testtube', 'test']
['ant', 'bank', 'testtubebabies', 'testtube', 'test', 'zeta11', 'zeta1', 'zz']

Answer 4

from functools import cmp_to_key

def custom_cmp(x, y):
    if x.startswith(y) or y.startswith(x):
        return len(y) - len(x)
    if x < y:
        return -1
    return 1

custom_key = cmp_to_key(custom_cmp)

a1 = ['test', 'testtube']
a1.sort(key=custom_key)
print(a1)
a2 = ['testtube', 'test']
a2.sort(key=custom_key)
print(a2)
a3 = ['bank', 'ant', 'testtube','test']
a3.sort(key=custom_key)
print(a3)

Результат:

['testtube', 'test']
['testtube', 'test']
['ant', 'bank', 'testtube', 'test']

Идея состоит в том, чтобы передать пользовательскую функцию ключа, которая создается путем преобразования компаратора (поскольку компараторы устарели в Python 3).

Answer 5

strList = ['tube','testtube']

print(strList)
a = strList.sort()
print(strList)

strList = ['bank', 'ant', 'testtube','tube']

print(strList)
a = strList.sort()
print(strList)

Результат:

['tube', 'testtube']

['testtube', 'tube']

['bank', ' ant ',' testtube ',' tube ']

[' ant ',' bank ',' testtube ',' tube ']