27

私は2つのリストを持っています、例えば：

keys1 = ['A', 'B', 'C', 'D', 'E',           'H', 'I']
keys2 = ['A', 'B',           'E', 'F', 'G', 'H',      'J', 'K']

両方のリストの順序を保持し、欠落している要素をそれらが属する場所に挿入して、重複のないマージされたリストを作成するにはどうすればよいですか？そのようです：

merged = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']

要素は等式と比較できますが、順序付けはできないことに注意してください（これらは複雑な文字列です）。要素を比較して並べ替えることはできませんが、元のリストでの出現に基づいて並べ替えられます。

矛盾する場合（両方の入力リストで順序が異なる）、すべての要素を含むすべての出力が有効です。もちろん、ソリューションがほとんどの注文を維持する上で「常識」を示している場合は、ボーナスポイントがあります。

繰り返しになりますが（一部のコメントはまだそれについて議論しています）、リストは通常​​、共通の要素の順序に関して互いに矛盾していません。その場合、アルゴリズムはそのエラーを適切に処理する必要があります。

.next（）を使用してリストを反復処理し、一致しない要素を含むリストだけを進めるバージョンから始めましたが、.next（）はいつ停止するかを知りません。

merged = []
L = iter(keys1)
H = iter(keys2)
l = L.next()
h = H.next()

for i in range(max(len(keys1, keys2))):
  if l == h:
    if l not in merged:
      merged.append(l)
    l = L.next()
    h = H.next()

  elif l not in keys2:
    if l not in merged:
      merged.append(l)
    l = L.next()

  elif h not in keys1:
    if h not in merged:
      merged.append(h)
    h = H.next()

  else: # just in case the input is badly ordered
    if l not in merged:
      merged.append(l)
    l = L.next()
    if h not in merged:
      merged.append(h)
    h = H.next()   

print merged

.next（）は最短リストの例外を引き起こすため、これは明らかに機能しません。これで、.next（）を呼び出すたびに、その例外をキャッチするようにコードを更新できました。しかし、コードはすでにかなり非Python的であり、これは明らかにバブルを破裂させるでしょう。

これらのリストを反復処理して要素を組み合わせる方法について、より良いアイデアを持っている人はいますか？

一度に3つのリストでそれができればボーナスポイント。

4

7 に答える 7

20

必要なのは、基本的に、マージユーティリティが行うことです。各シーケンスの相対的な順序を維持しながら、2つのシーケンスをマージしようとします。Pythonのdifflibモジュールを使用して、2つのシーケンスを比較し、それらをマージできます。

from difflib import SequenceMatcher

def merge_sequences(seq1,seq2):
    sm=SequenceMatcher(a=seq1,b=seq2)
    res = []
    for (op, start1, end1, start2, end2) in sm.get_opcodes():
        if op == 'equal' or op=='delete':
            #This range appears in both sequences, or only in the first one.
            res += seq1[start1:end1]
        elif op == 'insert':
            #This range appears in only the second sequence.
            res += seq2[start2:end2]
        elif op == 'replace':
            #There are different ranges in each sequence - add both.
            res += seq1[start1:end1]
            res += seq2[start2:end2]
    return res

例：

>>> keys1 = ['A', 'B', 'C', 'D', 'E',           'H', 'I']
>>> keys2 = ['A', 'B',           'E', 'F', 'G', 'H',      'J', 'K']
>>> merge_sequences(keys1, keys2)
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']

あなたが期待する答えは必ずしも唯一の可能なものではないことに注意してください。たとえば、ここでシーケンスの順序を変更すると、同じように有効な別の答えが得られます。

>>> merge_sequences(keys2, keys1)
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'I']
于 2013-01-09T16:48:22.453 に答える
3

最短の一般的なスーパーシーケンスの問題の解決策を求めているのではないかと思います。これは、任意の数の入力シーケンスの一般的なケースではNP困難であると私は信じています。この問題を解決するためのライブラリを私は知らないので、手動で実装する必要があるかもしれません。おそらく、コードを機能させる最も簡単な方法は、difflibを使用してinterjayの回答を取得し、それを使用reduceして任意の数のリストで実行することです（の3番目の引数として空のリストを指定してくださいreduce）。

于 2013-01-09T18:23:17.660 に答える
2

Set （cf. python doc）を使用して、2つのリストの要素を次々に入力します。

そして、それが終わったら、セットからリストを作成します。

あなたの質問には矛盾/パラドックスがあることに注意してください：あなたは比較できない要素の順序を維持したいです（あなたが言ったように「それらは複雑な文字列であるため」は平等だけです）。

編集：OPは、セットが挿入の順序を保持しないことに気づいています。

于 2013-01-09T16:07:33.623 に答える
1

リストのみを使用することで、いくつかの単純なforループと.copy()次の操作でこれを実現できます。

def mergeLists(list1, list2):
    # Exit if list2 is empty
    if not len(list2):
        return list1
    # Copy the content of list2 into merged list
    merged = list2.copy()

    # Create a list for storing temporary elements
    elements = []
    # Create a variable for storing previous element found in both lists
    previous = None

    # Loop through the elements of list1
    for e in list1:
        # Append the element to "elements" list if it's not in list2
        if e not in merged:
            elements.append(e)

        # If it is in list2 (is a common element)
        else:

            # Loop through the stored elements
            for x in elements:
                # Insert all the stored elements after the previous common element
                merged.insert(previous and merged.index(previous) + 1 or 0, x)
            # Save new common element to previous
            previous = e
            # Empty temporary elements
            del elements[:]

    # If no more common elements were found but there are elements still stored
    if len(elements)
        # Insert them after the previous match
        for e in elements:
            merged.insert(previous and merged.index(previous) + 1 or 0, e)
    # Return the merged list
    return merged

In [1]: keys1 = ["A", "B",      "D",      "F", "G", "H"]
In [2]: keys2 = ["A",      "C", "D", "E", "F",      "H"]
In [3]: mergeLists(keys1, keys2)
Out[3]: ["A", "B", "C", "D", "E", "F", "G", "H"]

英語は私の母国語ではなく、これを説明するのはかなり難しいですが、説明が気になる場合は、次のようにします。

  • elements一時的な要素を格納できるというローカル リストがあります。
  • previous両方のリストにあった前の要素を格納するというローカル変数があります。
  • list2にはないがにある要素を見つけると、list1その要素をリストに追加しelementsてループを続行します。
  • 両方のリストにある要素にヒットすると、リストをループし、elements要素の後のすべての要素を に追加しpreviousますlist2。
  • 次に、新しい一致が に格納されpreviousてelementsリセットされ[]、ループが続行されます。
  • 最初または最後の要素が両方のリストで共通要素でない場合、リストの最初と最後は共通要素としてカウントされます。

このようにして、常に次の形式に従います。

  1. 前の共通要素
  2. list1 の要素、2 つの共通要素の間
  3. list2 の要素、2 つの共通要素の間
  4. 新しい共通要素

たとえば、次のようになります。

l1 = ["A", "B", "C",      "E"]
l2 = ["A",           "D", "E"]
  1. 前の共通要素Aは、マージされたリストの最初になります。
  2. l1前の共通要素Aと新しい共通要素の間の要素は、 のE直後に挿入されAます。
  3. l2前の共通要素Aと新しい共通要素の間のE要素は、 の要素の直後に挿入されl1ます。
  4. 新しい共通要素Eは最後の要素になります。

  5. より一般的な要素が見つかった場合は、手順 1 に戻ります。

    [「A」、「B」、「C」、「D」、「E」]

于 2013-01-09T18:55:57.490 に答える