0

リストがあり、サブリスト、、、、、、、、、、およびx=[1, 2, 3, 4]が含まれているとします。しかし、x の 1 と 3 の間に 2 が現れるので、ギャップがあるため、 のようなものは含まれません。[1][2][3][4][1, 2][2, 3][3, 4][1,2,3][2,3,4][1,2,3,4][1, 3]

リストがギャップなしで別のリストに含まれているかどうかをテストする最良の方法を知っている人はいますか? for ループの解決策を考えましたが、あまり良い解決策ではないかもしれません。ありがとう。

4

5 に答える 5

3

あなたの質問は次のとおりです。

リストがギャップなしで別のリストに含まれているかどうかをテストする最良の方法を知っている人はいますか?

これは実際には、別の文字列から文字列を見つける問題と同じです。そのために、利用可能なアルゴリズムがたくさんあります。

Rabin–Karp、Boyer–Moore、Knuth–Morris などです。Boyer-Moore はその単純さから好きです。詳細はネットで調べてみてください。もちろん、リストが可能な位置から開始されているかどうかを確認することもできますが、複雑さは最適ではありません (そのような解決策はここで見つけることができます: Python でスライスされたリストの存在を確認してください)。

これがあなたのための簡単な（そして単純化された）実装です：

def boyer(x, sublist):
    p = len(sublist) - 1
    i = 0
    while i + p < len(x):
        if x[i + p] == sublist[p]:
            if p == 0:
                return True
            p -= 1
        elif x[i + p] in sublist:
            i += 1
            p = len(sublist) - 1
        else:
            i = i + p + 1
            p = len(sublist) - 1
    return False

このコードは慎重にテストする必要があり、力ずくのアプローチに代わる方法を示すことに注意してください。の時間計算量x[i + p] in sublistは線形であり、O(1) メソッドを取得するには別の方法で実装する必要があります。現在、そのため、力ずくのアプローチよりも優れているとは言えません。

于 2014-01-19T14:01:54.010 に答える
2

あなたが試すことができます

' '.join(str(c) for c in list1) in ' '.join(str(c) for c in list2)
于 2014-01-19T14:12:03.230 に答える
1 
sequences = [
    [1], [2],
    [1, 2], [2, 3], [3, 6],
    [1, 2, 3], [2, 3, 4], [1, 2, 3, 5],
]

bad_seq = lambda s: s and s != list(range(s[0], s[0] + len(s)))
print filter(bad_seq, sequences)   # [[3, 6], [1, 2, 3, 5]]
于 2014-01-19T14:55:43.397 に答える
0

メインリストのサブリストのインデックスで numpy-diff 関数を使用できます

In [427]: x=[1, 2, 3, 4]

In [428]: y = [1,3]

In [429]: z = [1,2,3]

In [430]: w = [2,1]

In [431]: import numpy as np

In [432]: sub_indices = [x.index(x1) for x1 in y]

これで、sub_indices は次のようになります: [0, 2] したがって、インデックス間の差分を確認できます。

In [433]: np.all(np.diff(sub_indices) == 1)
Out[433]: False

In [434]: sub_indices = [x.index(x1) for x1 in z]

In [435]: np.all(np.diff(sub_indices) == 1)
Out[435]: True

In [436]: sub_indices = [x.index(x1) for x1 in w]

In [437]: np.all(np.diff(sub_indices) == 1)
Out[437]: False
于 2014-01-19T14:55:58.367 に答える
0

別の解決策であり、その種の最善の方法がわからない場合は、質問を明確に理解できない場合はお知らせください。

ls = [[1], [2], [3], [4], [1, 2], [2, 3], [3, 6], [1, 2, 3], [2, 3, 4], [1, 2, 3, 5]]

def gap(l):
    for ls in l:
        result = list(set(map(lambda x: x[1] - x[0], zip(ls[0:], ls[1:]) )))
        if result and (len(result) > 1 or result[0] > 1):
            print ls
gap(ls)

出力: [3,6] [1, 2, 3, 5]

于 2014-01-19T14:40:03.517 に答える