python找不同數字的個數_在Python中跨多個清單查找最相似的數字

如果有一個既定的算法來做這件事，我不會感到驚訝，如果是的話，你應該使用它。但我不知道其中一個，是以我要推測一下。在

如果必須這樣做的話，我首先要做的就是周遊所有可能的數字組合，看看要花多長時間。如果你的資料集足夠小，就不值得花時間去發明一個聰明的算法。為了示範設定，我将包括示例代碼：# 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)

對于一個大的資料集，我會嘗試這樣的方法：首先為第一個清單中的每個數字建立一個三元組，其第一個條目設定為該數字。然後檢查這個部分填充的三元組的清單，對于每一個，從第二個清單中選擇最接近第一個清單中的數字的數字，并将其設定為三元組的第二個成員。然後仔細檢查三胞胎的清單，對于每個三胞胎，從第三個最接近前兩個數字的清單中選擇一個數字(根據您的協定度量)。最後，從中取其精華。此示例代碼示範如何使運作時在清單長度上保持線性。在

^{pr2}$

問題是，我可以想象這樣的情況，它實際上找不到最好的三元組，例如，如果第一個清單中的一個數字接近第二個清單中的一個，但與第三個清單中的任何一個都不接近。是以您可以嘗試對清單的所有6種可能的排序運作這個算法。我想不出一個具體的情況，那就是找不到最好的三胞胎，但其中一個可能仍然存在。在任何情況下，如果您使用一個聰明的實作，假設清單是排序的，那麼算法仍然是O(N)。在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 logn)，因為需要對對清單進行排序。在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

注意：我已經把這個答案中的所有代碼示例都寫得比你在實踐中做的更明确一點，以幫助你了解它們是如何工作的。但當你真的這麼做的時候，你會使用更多的清單了解和類似的東西。在

注2。不能保證代碼是有效的：-P但它應該能讓人大緻了解。在