1

大規模なアルゴリズムの一部としてこの問題に遭遇して解決しましたが、私の解決策は洗練されていないようで、洞察をいただければ幸いです。

デカルト平面上の点として表示できるペアのリストがあります。3 つのリストを生成する必要があります。並べ替えられた 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) に対応します。

このマッピング リストを生成する最も簡単な方法は何ですか?

4

4 に答える 4

3

簡単なO（nlog n）メソッドは次のとおりです。

  1. ペアをx値で並べ替えます：（（3、7）、（4、7）、（5、0）、（7、11）、（9、12）、（15、4））
  2. 最初のコンポーネントが前のリストの同じ位置からのy値であり、2番目のコンポーネントが0から増加するペアのリストを作成します：（（7、0）、（7、1）、（0、2）、（11 、3）、（12、4）、（4、5））
  3. このリストを最初のコンポーネント（y値）で並べ替えます：（（0、2）、（4、5）、（7、0）、（7、1）、（11、3）、（12、4））
  4. このリストを繰り返します。i番目のそのようなペア（y、k）については、yFor [k]=iに設定します。yFor []は、ソートされたxリストのインデックスをソートされたyリストのインデックスにマッピングするリスト（まあ、配列）です。
  5. 手順1で作成したリストから2番目の要素を削除するだけで、ソートされたxリストを作成します。
  6. 手順3で作成したリストと同じ操作を行って、ソートされたyリストを作成します。
于 2012-11-21T13:56:00.103 に答える
1

回答ありがとうございます。価値のあるものとして、私が持っていた解決策は概説したものとかなり似ていましたが、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]
于 2012-11-21T14:49:25.990 に答える
1

最初に x のポイントをソートすることにより、間接的なレベルを取り除くことによって j_random_hacker が何を意味するかを理解しました。そうすることで、物事をうまく整理することができます。ありがとう。

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
于 2012-11-21T15:42:01.513 に答える
1

以下を提案します。ソートされていない x リストと y リストを生成します。

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

各要素をタプルに変換します。最初のペアは座標で、2 番目は元のインデックスです。

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。の各要素について、タプルの 2 番目のペアであるxsを取得します。指定された で y 要素の現在のインデックスを取得するためにoriginal_index使用します。現在のインデックスを に追加します。y_positionsoriginal_indexindex_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) 時間であるため、全体としてのアルゴリズムの複雑さは、並べ替えステップによって支配されます。

于 2012-11-21T13:41:28.560 に答える