0

したがって、次の 2 つの異なるリストがあります。

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

私の目標は、これら 2 つのリストの最小の違いを見つけることです。d(x,y)との 2 つの要素の差を与えるx関数が定義されていますy。リスト 1 の各要素は、リスト 2 の 1 つまたはゼロの要素に一致します。一致しない要素には、 によって与えられる「差異」もありますd(a)。

これを行うための最良のアルゴリズムが何であるか、またはどのように行うかはわかりません。関連する場合、私はPythonで作業しています。

4

3 に答える 3

1

二部グラフでのマッチングが必要だと思います: 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 の要素ごとに 1 つの接続)。Sum(Aij over j) = 1 (list2 の要素ごとに 1 つの接続)。ここで、目的関数 sum(d(list1[i], list2[j])*Aij) を最大化/最小化します。長さリスト 1 != 長さリスト 2 の場合は、追加の変数を追加して、一部の変数がコスト d(x) でそれ自体に接続できるようにし、それを目的関数に追加する必要があることを忘れないでください。

于 2013-02-13T10:16:06.710 に答える
0

あなたが求めているのは、基本的に2つのリストに共通するすべての要素を見つけることであるかどうかはよくわかりません.

その場合、これはうまくいくかもしれません：

list1 = [1,2,3,4]
list2 = [3,4,5]
diff = set(list1).intersection(set(list2))
于 2013-02-13T10:20:45.220 に答える
0

質問は少し曖昧だと思いますが、私の刺し傷は次のとおりです。

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-13T11:30:03.497 に答える