找到兩個不同大小的數組

所以所有的匹配問題，我有兩個不同的表，說：找到兩個不同大小的數組

list1 = [a,b,c,d] 
list2 = [e,f,g]

我的目標是要找出這兩個列表之間的最小差值。我有一個定義的功能d(x,y)，它給出了兩個元素x和y之間的差異。它們如此匹配：list1中的每個元素都與list2中的一個或零個元素相匹配。無與倫比的元素也有d(a)給出的「差異」。

我不確定這樣做的最佳算法是什麼，或者我該如何去做。如果相關，我正在Python中工作。

來源

2013-02-13 rj29

數組？你是指名單？無論如何，看看'difflib'：http://docs.python.org/2/library/difflib.html – eumiro 2013-02-13 10:09:10

是的。我的語言有點sl- - python不是我的第一語言。 – rj29 2013-02-13 10:11:15

我想你想要在二分圖中匹配： http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs 你應該使用匹配算法。如果你不能作爲最後的手段使用整數編程。 Pulp是一個適合整數編程的python包。整數編程包將會慢得多，但可能更容易編碼。

如果您選擇使用整數編程，約束是變量Aij表示list1 [i]和list2 [j]之間的連接。 Aij = 1或0.（連接打開或關閉）。 Sum（Aij over i）= 1（每個元素在list1中一個連接）。 Sum（Aij over j）= 1（每個元素在列表2中有一個連接）。現在你想最大化/最小化目標函數和（d（list1 [i]，list2 [j]）* Aij）。不要忘記，如果長度爲list1！= length2，則必須添加額外的變量以允許某些變量通過成本d（x）連接到自身，並將其添加到目標函數中。

來源

2013-02-13 10:16:06

我不太確定你所問的基本上是找到兩個列表之間的所有共同元素。

在這種情況下，這可能工作：

list1 = [1,2,3,4] 
list2 = [3,4,5] 
diff = set(list1).intersection(set(list2))

來源

2013-02-13 10:20:45 drekyn

我不認爲他在問這個問題 – 2013-02-13 10:26:38

我認爲這個問題是有點含糊，但我在這刺是以下幾點：

雖然我不知道OP期待列表或類似產品。

也許如果OP查看itertools-functions他們可能會看到適合的東西。

import random 

list1 = random.sample(range(50), 3) 
list2 = random.sample(range(50), 2) 

print "List1", list1 
print "List2", list2 


def router(a, b): 
    print "ROUTER", a, b 
    if a == None: 
     return b * 10 
    elif b == None: 
     return a * 10 
    else: 
     return (a + b) * 10 


print map(router, list1, list2) 

########################## 
# Using itertools.product 
########################## 
import itertools 

def pair(p): 
    a, b = p 
    print "PAIR", a, b 
    if a == None: 
     return b * 10 
    elif b == None: 
     return a * 10 
    else: 
     return (a + b) * 10 

product = itertools.product(*zip(*map(None, list1, list2))) 

print map(pair, product)

輸出

List1 [17, 48, 9] 
List2 [45, 42] 
ROUTER 17 45 
ROUTER 48 42 
ROUTER 9 None 
[620, 900, 90] 
PAIR 17 45 
PAIR 17 42 
PAIR 17 None 
PAIR 48 45 
PAIR 48 42 
PAIR 48 None 
PAIR 9 45 
PAIR 9 42 
PAIR 9 None 
[620, 590, 170, 930, 900, 480, 540, 510, 90]

來源

2013-02-13 11:30:03 sotapme

找到兩個不同大小的數組

回答

相關問題