сортировать массив на основе пользовательского алфавита порядка Python

Question

Я хочу написать код для сортировки arr на основе порядка customAl, а не использовать отсортированную функцию.

customAl = [dshbanfmg]
arr = [bba,abb,baa,mggfba,mffgh......]

псевдокод:

def sortCA(arr, customAl):
    dt = {}
    generate dt order based on customAl
    look up and sort arr

    return result


newArr = [bba,baa,abb,mffgh,mggfba......]

Я знаю, что есть похожий вопрос, но ответ обернут в отсортированную функцию, которую я не хочу использовать. У кого-нибудь есть лучшее решение, чем несортированный или словарь, который занимает место?

Сортировка строковых значений в соответствии с пользовательским алфавитом в Python

Answer 1

На мой взгляд, программирование - это компромисс, оно зависит от того, какая часть вас волнует больше всего.

В частности, в этом сценарии вы можете обменять время на пространство на str.index или обменять пространство на время с дополнительным индексом dict:

customAl = 'dshbanfmg'
arr = ['bba', 'abb', 'baa', 'mggfba', 'mffgh']

# trade time for space
# no extra space but, but O(n) to index
def sortCA1(arr, customAl):
    return sorted(arr, key=lambda x: [customAl.index(c) for c in x])

# trade space for time
# extra space O(n), but O(1) to index
def sortCA2(arr, customAl):
    dt = {c: i for i, c in enumerate(customAl)}
    return sorted(arr, key=lambda x: [dt[c] for c in x])

# output: ['bba', 'baa', 'abb', 'mffgh', 'mggfba']

---

Вот версия, которая не использует функцию sorted, мы можем использовать корзину, основанную на произвольном порядке алфавита.разделить arr на 1-ый символ, если в одном сегменте есть несколько элементов, а затем рекурсивно разделить на 2-ой символ ... вид сортировки по основанию: одна вещь, которую нужно упомянуть, длина другая, поэтому мы должны добавить контейнер для записи без индекса str.

def sortCA3(arr, customAl):
    dt = {c: i + 1 for i, c in enumerate(customAl)}  # keep 0 for none bucket

    def bucket_sort(arr, start):
        new_arr = []
        buckets = [[] for _ in range(len(customAl) + 1)]

        for s in arr:
            if start < len(s):
                buckets[dt[s[start]]].append(s)
            else:
                buckets[0].append(s)

        for bucket in buckets:
            if len(bucket) == 1:
                new_arr += bucket
            elif len(bucket) > 1:
                new_arr += bucket_sort(bucket, start+1)
        return new_arr

    return bucket_sort(arr, 0)

тест и вывод

customAl = 'dshbanfmg'
arr = ['bba', 'bb', 'abb', 'baa', 'mggfba', 'mffgh']  # add `bb` for test
print(sortCA4(arr, customAl))