根据另一个按步骤排序的列表对列表进行排序

Question

我正在尝试根据列表 A 的排序对列表 B 进行排序。棘手的部分是列表 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)

发生以下情况：

A 中的子列表 0 根据长度倒序排序，然后是子列表 1,2，然后是 3,4，最后是 5,6。

Answer 1

您可以使用 zip 对列表进行排序，您只需要一个可以解释对的关键函数。然后，一旦你对这些对进行排序，你就可以使用 zip

'unzip' 它们

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

Answer 2

假设 A 中的所有对象都是可哈希且唯一的：

将 A 和 B 一起压缩到列表 C 中并将该列表放在一边。
使用基于神秘步骤的算法对 A 进行排序。不用担心 B 或 C
排序完成后，构建一个包含 A 项的反向查找字典到排序算法放置它们的位置。
使用反向查找和压缩列表进行排序 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 的 zip 排序在一起，这在另一个答案中有描述。

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)

根据另一个按步骤排序的列表对列表进行排序

Sorting a list based on another list which is sorted in steps

python

list

sorting

sublist