4

私はこの質問が重複しているように見えるかもしれないことを知っています。しかし、私はこれを解決しようとするのに苦労しました、そして私は私の場合に役立つ解決策を見つけることができませんでした

私は巡回セールスマン問題のためにPythonを使用して遺伝的アルゴリズムを実装しています

それらのリストがあると仮定します（ツアー）

a = [1,0,2,5,4,3,1]
b = [1,2,5,4,3,0,1]
c = [1,3,5,4,2,0,1]

ご覧のとおり、[5,4]は3つのリスト全体で繰り返され、通常の交差はリスト内のすべての要素を返します。

私はintersect_list（a、b）のようないくつかの関数が欲しい

[5,4]を返します

これを見つけるためのPython組み込みの方法はありますか？または何か提案がありますか？

注：これを解決するためにループできることはわかっていますが、私の場合は約400のリストがあることに注意してください。そしてそれぞれ401の長さで。

言い換えれば、私はそれらのリスト間の共通のパスを見たいのです。

不明な点がございましたら、事前にお知らせください。

4

4 に答える 4

3

@pyfunc によって投稿されたリンクを見た後、次のことを思いつきました。

def shortest_of(lists):
    return min(lists, key=len)

def contains_sublist(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1)) 

def longest_common(lists):
    if not lists:
        return ()
    res = set()    
    base = shortest_of(lists)
    length = len(base)

    for i in xrange(length, 0, -1):
        for j in xrange(length - i + 1):
            candidate = ', ' + str(base[j:i+j]).strip('[]') + ','
            #candidate = base[j:i+j]  

            for alist in lists:
                if not candidate in ', ' + str(alist).strip('[]') + ',':
                #if not contains_sublist(alist, candidate):   
                    break
            else:
                res.add(tuple([int(a) for a in candidate[2:-1].split(',')]))
                #res.add(tuple(candidate))

        if res:
            return tuple(res)    

    return ()

if __name__ == '__main__':
    a = [1,0,2,5,4,3,1]
    b = [1,2,5,4,3,0,1]
    c = [1,3,5,4,2,0,1]

    print longest_common([a,b,c])
    print longest_common([b,c])

出力：

((5, 4),)
((0, 1), (5, 4))

編集：

文字列の変換とマッチングを使用するようにソリューションを更新しました。たまたま高速でした。以前のソリューション部分はコメント アウトされています。また、すべての可能性を提供するようになりました。

于 2012-06-08T02:25:43.797 に答える
1

1つのアイデアは、リストを次の文字列に変換できることです。

",".join(list)

次に、問題は2つの文字列の中で最も長く一致する部分文字列に変換されます。

そのための解決策と議論はSOにあります：

  1. 3つ以上の文字列からの最長の共通部分文字列-Python
  2. http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python
于 2012-06-08T00:10:42.980 に答える
1

長さ 400 の 400 個のリストは、それほど大きな問題ではありません。最初に、各シーケンスを可能なすべてのサブシーケンスに分割します (長さのリストには、可能なサブシーケンスが含まれますN) 0.5 * N ** 2。次に、それらすべてを交差させ、最も長いものを取ります。

a = [1,0,2,5,4,3,1]
b = [1,2,5,4,3,0,1]
c = [1,3,5,4,2,0,1]

def longest_match_finder(lists):
    matches = []
    for a in lists:
        lengths = set()
        for leng in xrange(1,len(a)+1):
            lengths = lengths | set(tuple(a[i:i+leng]) 
                                    for i in xrange(len(a)-leng+1))
        matches.append(lengths)
    return max(set.intersection(*matches), key=len)

print longest_match_finder([a,b,c])
#Output:
(5, 4)

それぞれに要素を400持つリストを使用すると、これがうまくいきます（私の非常に古いマシンで）。ただし、1 つのリストだけで同じアプローチを使用し、そのサブシーケンスと他のすべてのリストを文字列に変換すると (@pyfunc によって最初に投稿されたように)、 を使用して、はるかに迅速に検索できます。同じテストが次の場所で実行されます。400280 secondsstr(list).strip('[]')21 seconds

import ast

def longest_match_finder_2(lists):
    a = lists[0]
    lengths = set()
    for leng in xrange(1,len(a)+1):
        lengths = lengths | set(str(a[i:i+leng]).strip('[]') 
                                for i in xrange(len(a)-leng+1))
    for seq in lengths.copy():
        if not all([seq in str(i).strip('[]') for i in lists[1:]]):
            lengths.remove(seq)
    return ast.literal_eval(max(lengths, key=len))

ast.literal_eval()最後に（安全に）リストを取得するために使用できます。

于 2012-06-08T00:46:12.720 に答える
-1

list zip関数を使用してそれらをタプルに圧縮し、すべての要素が同じタプルを返すことができます。

a = [1,0,2,5,4,3,1]
b = [1,2,5,4,3,0,1]
c = [1,3,5,4,2,0,1]
zipped_tuples = zip(a, b, c)

これを利用して、位置の交差を取得することができます。

于 2012-06-08T00:18:21.360 に答える