python - 对列表列表中的值进行排序

Question

我有一个列表列表 A长度 m . A的每一个列表包含来自 {1, 2, ..., n} 的正数.下面是一个例子，其中m = 3和 n = 4 .

A = [[1, 1, 3], [1, 2], [1, 1, 2, 4]]

我代表每个数字x在 A作为一对(i, j)在哪里 A[i][j] = x .我想对 A 中的数字进行排序按非递减顺序；按最低的第一指数打破平局。也就是说，如果 A[i1][j1] == A[i2][j2] ，然后 (i1, j1)出现在 (i2, j2) 之前如果i1 <= i2 .

在示例中，我想返回对:

(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)

表示排序后的数字

1, 1, 1, 1, 1, 2, 2, 3, 4

我所做的是一种天真的方法，其工作原理如下:

• 首先我对 A 中的每个列表进行排序.
• 然后我迭代 {1, 2, ..., n} 中的数字和列表 A并添加对。

代码:

for i in range(m): 
    A[i].sort()
S = []
for x in range(1, n+1):
    for i in range(m):
        for j in range(len(A[i])):
            if A[i][j] == x:
                S.append((i, j))

我认为这种方法不好。我们能做得更好吗？

Answer 1

您可以制作 (x, i, j) 的 三元组，对这些三元组进行排序，然后提取索引 (i, j) .这是有效的，因为三元组包含排序所需的所有信息，并按排序所需的顺序包含在最终列表中。 (这被称为“装饰-排序-不装饰”习语，与 Schwartzian 变换有关——Hat-tip 到 @Morgen 的名称和概括以及我解释这种技术的普遍性的动机。)这可以结合起来成一个语句，但为了清楚起见，我在这里将其拆分。

A = [[1, 1, 3], [1, 2], [1, 1, 2, 4]]

triplets = [(x, i, j) for i, row in enumerate(A) for j, x in enumerate(row)]
pairs = [(i, j) for x, i, j in sorted(triplets)]
print(pairs)

这是打印结果:

[(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)]