Сортировка списка на основе другого списка, отсортированного по шагам - PullRequest
Новая
       25

Сортировка списка на основе другого списка, отсортированного по шагам

0 голосов
/ 10 июля 2019

Я пытаюсь отсортировать список B на основе сортировки списка A.Сложность в том, что сортировка списка A выполняется пошагово.Я попытался сжать списки, но я просто не могу заставить его работать.

Сортировка списка A выполняется следующим образом: 

steps = [0, 1, 3, 5]
B = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
A = [['X', 'Y'], ['X'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'], ['X'], ['X', 'Y', 'Z'], ['X', 'Y']

for i in range(len(steps)-1):
    A[steps[i]:steps[i + 1]] = sorted(A[steps[i]:steps[i + 1]], key = len, reverse=True)

Происходит следующее:

подсписок 0 в A сортируется по длинев обратном порядке, затем подсписки 1,2, затем 3,4 и, наконец, 5,6.

Ответы [ 2 ]

1 голос
/ 10 июля 2019

Предполагая, что все объекты в A являются хэшируемыми и уникальными:

  1. Застегните A и B вместе в список C и отложите этот список в сторону.
  2. Сортировка A, используя ваш загадочный пошаговый алгоритм. Не беспокойтесь о B или C
  3. Когда сортировка завершится, создайте словарь обратного просмотра из A элементов, куда их поместит алгоритм сортировки.
  4. Используйте этот обратный поиск и сжатый список для сортировки B. 
A = [29, 42, 17]
B = ['bravo', 'charlie', 'alpha']
C = list(zip(A, B))
A.sort() # replace with your mystery sorter
lookup = {a:index for (index, a) in enumerate(A)}

for  (a, b) in C:
    index = lookup[a]
    B[index] = b

print(A)
print(B)

#output
[17, 29, 42]
['alpha', 'bravo', 'charlie']

Стоимость сборки C, построения справочника поиска и организации B в конце - O (n)

Отказ от ответственности: не любитель писать обратно в B. Предпочел бы написать в новый список, который был правильно настроен.

Обновление: Приведенный выше код работает только в том случае, если в A. нет дубликатов. Фрагмент кода ниже обрабатывает дубликаты, добавляя фрагмент уникальности (исходный индекс). Хотя это работает, подход слишком запутанный. Вы также можете отсортировать почтовые индексы A и B вместе, что описано в другом ответе. 

A = [29, 42, 29, 17]
B = ['bravo1', 'charlie', 'bravo2', 'alpha']
A2 = [(index, a) for index,a in enumerate(A)]
C = list(zip(A, B))
A2.sort(key=lambda t : t[1] ) # replace with your mystery sorter, which has to deal with tuples now
A = [a for (_, a) in A2]
lookup = {t:index for (index, t) in enumerate(A2)}

for  original_index, (a, b) in enumerate(C):
    new_index = lookup[original_index, a]
    B[new_index] = b

print(A)
print(B)

#output
[17, 29, 29, 42]
['alpha', 'bravo1', 'bravo2', 'charlie']

Для полноты приведенный ниже код - это то, что я действительно сделал бы, если бы мне пришлось иметь дело с дубликатами в A. Это, по сути, другой ответ, который был опубликован. 

A = [29, 42, 29, 17]
B = ['bravo1', 'charlie', 'bravo2', 'alpha']
C = list(zip(A, B))
C.sort(key=lambda t : t[0] ) # replace with your mystery sorter, which has to deal with a zip of A and B together
[A, B] = zip(*C)

print(A)
print(B)
1 голос
/ 10 июля 2019

Вы можете использовать zip для сортировки списков, вам просто нужна ключевая функция, которая может интерпретировать пары.Затем, как только вы отсортируете пары, вы можете распаковать их, используя zip 

B = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
A = [['X', 'Y'], ['X'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'], ['X'], ['X', 'Y', 'Z'], ['X', 'Y']]
def lenRight(pair):
    return len(pair[1])
C = sorted(zip(B,A), key = lenRight)

B_sorted, A_sorted = zip(*C)
print(B_sorted)
print(A_sorted)

Это выдаст: 

('B', 'E', 'A', 'G', 'C', 'D', 'F')
(['X'], ['X'], ['X', 'Y'], ['X', 'Y'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'])

РЕДАКТИРОВАТЬ:

Теперь я понимаю, 

steps = [1, 3, 5]
B = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
A = [['X', 'Y'], ['X'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'], ['X'], ['X', 'Y', 'Z'], ['X', 'Y']]

lastStep = 0
sortedLists = []

def lenRight(pair):
        return len(pair[1])

for step in steps:
    C = sorted(zip(B[lastStep:lastStep+step],A[lastStep:lastStep+step]), key = lenRight, reverse = True)

    B_sorted, A_sorted = zip(*C)
    sortedLists.append((A_sorted, B_sorted))

    lastStep = step

for pair in sortedLists:
    A_sort, B_sort = pair
    print(A_sort, B_sort)

Выходы: 

(['X', 'Y'],) ('A',)
(['X', 'Y', 'Z'], ['X', 'Y', 'Z'], ['X']) ('C', 'D', 'B')
(['X', 'Y', 'Z'], ['X', 'Y', 'Z'], ['X', 'Y'], ['X']) ('D', 'F', 'G', 'E')
...