在Python中,我有3个浮点数列表(角度),范围为0-360,并且这些列表的长度不同。我需要找到三元组(每个列表中取一个数字),使得它们之间的距离最小。(由于这是实际数据,很不可能存在任何相同的数字)。我考虑使用一种简单的最小标准差方法来衡量协议,但我不确定如何有效地实现它。我可以通过嵌套for循环遍历每个列表,比较每个可能组合的标准差,并且使用一个临时变量保存最佳匹配的三元组的索引位置,但我想知道是否有更好、更优雅的方法来完成类似的操作。谢谢!
如果有针对此操作的已建立算法,我不会感到惊讶,如果有的话,您应该使用它。但是我不知道有没有这样的算法,所以我会稍微猜测一下。
如果我必须执行此操作,我会尝试的第一件事就是循环遍历所有可能的数字组合,并查看执行时间。如果您的数据集足够小,则不值得花费时间来发明一个聪明的算法。为了演示设置,我将包括示例代码:
# setup
def distance(nplet):
'''Takes a pair or triplet (an "n-plet") as a list, and returns its distance.
A smaller return value means better agreement.'''
# your choice of implementation here. Example:
return variance(nplet)
# algorithm
def brute_force(*lists):
return min(itertools.product(*lists), key = distance)
def item_selection(listA, listB, listC):
# make the list of partially-filled triplets
triplets = [[a] for a in listA]
iT = 0
iB = 0
while iT < len(triplets):
# make iB the index of a value in listB closes to triplets[iT][0]
while iB < len(listB) and listB[iB] < triplets[iT][0]:
iB += 1
if iB == 0:
triplets[iT].append(listB[0])
elif iB == len(listB)
triplets[iT].append(listB[-1])
else:
# look at the values in listB just below and just above triplets[iT][0]
# and add the closer one as the second member of the triplet
dist_lower = distance([triplets[iT][0], listB[iB]])
dist_upper = distance([triplets[iT][0], listB[iB + 1]])
if dist_lower < dist_upper:
triplets[iT].append(listB[iB])
elif dist_lower > dist_upper:
triplets[iT].append(listB[iB + 1])
else:
# if they are equidistant, add both
triplets[iT].append(listB[iB])
iT += 1
triplets[iT:iT] = [triplets[iT-1][0], listB[iB + 1]]
iT += 1
# then another loop while iT < len(triplets) to add in the numbers from listC
return min(triplets, key = distance)
def symmetrized_item_selection(listA, listB, listC):
best_results = []
for ordering in itertools.permutations([listA, listB, listC]):
best_results.extend(item_selection(*ordering))
return min(best_results, key = distance)
另一个选择是计算列表1和列表2之间、列表1和列表3之间以及列表2和列表3之间的所有可能数字对。然后将这三个数字对列表一起排序,从最好到最差的一致性排序。从最接近的数字对开始,逐对浏览该列表,每当遇到与已经看过的数字对共享数字的数字对时,将它们合并成三元组。对于一种合适的一致性度量,一旦找到第一个三元组,那将给出您需要迭代的最大对距离,一旦达到它,您只需选择您找到的最接近的三元组即可。我认为这应该始终能够找到最佳的三元组,但由于需要对数字对列表进行排序,所以时间复杂度为O(N^2 log N)。
def pair_sorting(listA, listB, listC):
# make all possible pairs of values from two lists
# each pair has the structure ((number, origin_list),(number, origin_list))
# so we know which lists the numbers came from
all_pairs = []
all_pairs += [((nA,0), (nB,1)) for (nA,nB) in itertools.product(listA,listB)]
all_pairs += [((nA,0), (nC,2)) for (nA,nC) in itertools.product(listA,listC)]
all_pairs += [((nB,1), (nC,2)) for (nB,nC) in itertools.product(listB,listC)]
all_pairs.sort(key = lambda p: distance(p[0][0], p[1][0]))
# make a dict to track which (number, origin_list)s we've already seen
pairs_by_number_and_list = collections.defaultdict(list)
min_distance = INFINITY
min_triplet = None
# start with the closest pair
for pair in all_pairs:
# for the first value of the current pair, see if we've seen that particular
# (number, origin_list) combination before
for pair2 in pairs_by_number_and_list[pair[0]]:
# if so, that means the current pair shares its first value with
# another pair, so put the 3 unique values together to make a triplet
this_triplet = (pair[1][0], pair2[0][0], pair2[1][0])
# check if the triplet agrees more than the previous best triplet
this_distance = distance(this_triplet)
if this_distance < min_distance:
min_triplet = this_triplet
min_distance = this_distance
# do the same thing but checking the second element of the current pair
for pair2 in pairs_by_number_and_list[pair[1]]:
this_triplet = (pair[0][0], pair2[0][0], pair2[1][0])
this_distance = distance(this_triplet)
if this_distance < min_distance:
min_triplet = this_triplet
min_distance = this_distance
# finally, add the current pair to the list of pairs we've seen
pairs_by_number_and_list[pair[0]].append(pair)
pairs_by_number_and_list[pair[1]].append(pair)
return min_triplet