映射排序索引

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