映射排序索引

Question

我遇到并解决了这个问题作为一个更大的算法的一部分，但我的解决方案似乎不雅，我会感谢任何见解。

我有一对可以在笛卡尔飞机上看作点的列表。我需要生成三个列表：排序后的x值，排序后的y值以及将已排序的x值中的索引与已排序的y值中的索引进行映射（与最初配对的y值相对应）。

一个具体的例子可能有助于解释。给出以下列表：

（（3,7），（15,4），（7,11），（5,0），（4,7），（9,12））

x值的排序列表将是（3,4,5,7,9,15），y值的排序列表将是（0,4,7,7,11,12）。

假设基于零的索引方案，将x列表索引映射到其配对的y列表索引的索引的列表将为（2,3,0,4,5,1）。

例如，值7在x列表中显示为索引3。索引3处映射列表中的值为4，y列表中索引4处的值为11，对应于原始配对（7,11）。

生成此映射列表的最简单方法是什么？

Answer 1

下面是一个简单O（n日志n）的方法：

1. 排序的对通过它们的x值：（（3,7），（4,7），（5,0），（7， 11），（9，12），（15，4））
2. 生成一个对列表，其中第一个分量是来自上一个列表中相同位置的y值，第二个分量从0开始增加：（ （y值）：（（），（0,1），（0,2），（11,3）， （0，2），（4,5），（7,0），（7,1），（11,3），（12,4））
3. 迭代通过此lis吨。对于第i对这样的对（y，k），设置yFor [k] = i。 yFor []是您排序的x列表中索引映射到排序的y列表中的索引的列表（well，array）。
4. 只需从步骤1
5. 产生的列表中删除第二个元素做同样的，在步骤产生的列表创建排序Ÿ列表创建排序X清单3.

Answer 2

我建议如下。 生成未排序的x和y列表。

xs = [3, 15, 7, 5, 4, 9 ] 
ys = [7, 4, 11, 0, 7, 12] 

将每个元素转换为一个元组 - 第一对是坐标，第二个是原始索引。

xs = [(3, 0), (15, 1), (7, 2), (5, 3), (4, 4), (9, 5)] 
ys = [(7, 0), (4, 1), (11, 2), (0, 3), (7, 4), (12, 5)] 

对两个列表进行排序。

xs = [(3, 0), (4, 4), (5, 3), (7, 2), (9, 5), (15, 1)] 
ys = [(0, 3), (4, 1), (7, 0), (7, 4), (11, 2), (12, 5)] 

创建一个数组，y_positions。数组的第n个元素包含最初在索引n处的y元素的当前索引。

创建一个空的index_list。 对于xs的每个元素，获取第二对元组original_index。 使用y_positions检索给定original_index的y元素的当前索引。将当前索引添加到index_list。

最后，从xs和ys中删除索引值。

下面是一个示例Python实现。

points = ((3, 7), (15, 4), (7, 11), (5, 0), (4, 7), (9, 12)) 

#generate unsorted lists 
xs, ys = zip(*points) 

#pair each element with its index 
xs = zip(xs, range(len(xs))) 
ys = zip(ys, range(len(xs))) 

#sort 
xs.sort() 
ys.sort() 

#generate the y positions list. 
y_positions = [None] * len(ys) 
for i in range(len(ys)): 
    original_index = ys[i][1] 
    y_positions[original_index] = i 

#generate `index_list` 
index_list = [] 
for x, original_index in xs: 
    index_list.append(y_positions[original_index]) 

#remove tuples from x and y lists 
xs = zip(*xs)[0] 
ys = zip(*ys)[0] 

print "xs:", xs 
print "ys:", ys 
print "index list:", index_list 

输出：

xs: (3, 4, 5, 7, 9, 15) 
ys: (0, 4, 7, 7, 11, 12) 
index list: [2, 3, 0, 4, 5, 1] 

的y_positions和index_list代是O（n）的时间，所以作为一个整体，通过分选步骤控制了算法的复杂性。

Answer 3

谢谢为答案。对于它的价值，我提供的解决方案非常类似于这些概述，但正如j_random_hacker指出的那样，不需要映射。这让我觉得这个小问题似乎比乍看起来更复杂，我想知道我是否错过了一些明显的东西。我将我的解决方案重新编译为Python以供比较。

points = ((3, 7), (15, 4), (7, 11), (5, 0), (4, 7), (9, 12)) 

N = len(points) 

# Separate the points into their x and y components, tag the values with 
# their index into the points list. 

# Sort both resulting (value, tag) lists and then unzip them into lists of 
# sorted x and y values and the tag information. 

xs, s = zip(*sorted(zip([x for (x, y) in points], range(N)))) 
ys, r = zip(*sorted(zip([y for (x, y) in points], range(N)))) 

# Generate the mapping list. 

t = N * [0] 

for i in range(N): 
    t[r[i]] = i 

index_list = [t[j] for j in s] 

print "xs:", xs 
print "ys:", ys 
print "index_list:", index_list 

输出：

xs: (3, 4, 5, 7, 9, 15) 
ys: (0, 4, 7, 7, 11, 12) 
index_list: [2, 3, 0, 4, 5, 1] 

Answer 4

我刚刚明白了什么j_random_hacker通过在X初步排序，点删除了一个间接层意思。这样可以很好地整理东西。谢谢。

points = ((3, 7), (15, 4), (7, 11), (5, 0), (4, 7), (9, 12)) 

N = len(points) 

ordered_by_x = sorted(points) 
ordered_by_y = sorted(zip([y for (x, y) in ordered_by_x], range(N))) 

index_list = N * [0] 

for i, (y, k) in enumerate(ordered_by_y): 
    index_list[k] = i 

xs = [x for (x, y) in ordered_by_x] 
ys = [y for (y, k) in ordered_by_y] 

print "xs:", xs 
print "ys:", ys 
print "index_list:", index_list