5

数値を含む一連の文字列が与えられた場合、スーパーセットである文字列を見つけるにはどうすればよいですか。たとえば、文字列 '139 24' と '139 277 24' が表示された場合、'139 24' はその中にあるため、'139 277 24' を保持します。また、これらの数値は、文字列内で任意の順序で表示される場合があります。

               '24'
              '277'
           '277 24'
           '139 24'
       '139 277 24'
          '139 277'
              '139'
           '136 24'
       '136 277 24'
          '136 277'
              '136'
       '136 139 24'
   '136 139 277 24'
      '136 139 277'
          '136 139'
              '246'

上記のデータの結果を以下に示します。

   '136 139 277 24'
              '246'

編集:各文字列を分割し、個々の数字をセットに入れ、リスト全体から作成されたセットでこれを比較しています。このアプローチを使用して解決策を見つけることができますが、同じことを実行する他のエレガントな方法があるはずです。

次のコードを試していて、不必要に複雑になっていると感じました。

#First create a set of tuples
allSeqsTuple = set()
for seq in allSeqs: #allSeqs store the sequences described above
    x = seq.split()
    allSeqsTuple.add(tuple(x))


#For each 'allSeqs', find if all the items in that seq that is in 'allSeqsTuple'. 
for line in allSeqs:
    x = set(line.split())
    result = findContainment(x, allSeqsTuple)
    ......
    ......

def findContainment(x, allSeqsTuple):
    contained = False
    for y in allSeqsTuple:
        cntnd = bool(x-set(y))
        if (cntnd):
            contained = True
            continue
        else:
            break
    return contained
4

2 に答える 2

7

この問題の主要なプレーヤーの長いリストを作成しましょう。

  • 文字列、例えば'24 139 277'
  • セット -- 「スーパーストリング」のコレクション
  • スーパーセットの包含 --<=セット演算子
  • 文字列を一連の数値文字列に分割する: 例set(['24', '139', '277'])

文字列のリストが与えられますが、本当に必要なのは、より便利なセットのリストです。

In [20]: strings = [frozenset(s.split()) for s in strings]    
In [21]: strings
Out[21]: 
[frozenset(['24']),
 frozenset(['277']),
 ...
 frozenset(['136', '139']),
 frozenset(['246'])]

凍結セットの理由はすぐに明らかになります。その理由を以下で説明します。セットが必要な理由は、便利なスーパーセット比較演算子があるためです。

In [22]: frozenset(['136']) <= frozenset(['136', '139', '24'])
Out[22]: True

In [23]: frozenset(['136']) <= frozenset(['24', '277'])
Out[23]: False

これはまさに、ある文字列が別の文字列のスーパーストリングかどうかを判断するために必要なものです。

したがって、基本的には、次のことを行います。

  • の空のセットから始めますsuperstrings = set()
  • 文字列を反復処理: for s in strings.
  • sでそれぞれを調べて、それらが既に にあるアイテムのサブセットでない場合は strings、新しいものを に追加 します。superstringssuperstrings

  • ごとsに、一連のsuperstrings:を反復処理しますfor sup in superstrings。

    • をチェックしますs <= sup-- つまり、sが のサブセットである場合、は既知のスーパーストリングよりも小さいsupため、ループを終了します。s

    • かどうかを確認しますsup <= s-- つまり、 s内のアイテムのスーパーセットかどうかsuperstrings。この場合、 のアイテムを削除し、superstringsに置き換えsます。

テクニカルノート:

  • からアイテムを削除しているためsuperstrings、それ自体を反復することもできませんsuperstrings。したがって、代わりに、コピーを反復処理します。

    for sup in superstrings.copy():
  • superstrings最後に、セットのセットになりたいと思います。ただし、セット内のアイテムはハッシュ可能である必要があり、セット自体はハッシュ可能ではありません。ただし、frozensets はそうであるため、frozensets のセットを持つことは可能です。stringsこれが、 のリストに 変換した理由ですfrozensets。
strings = [
    '24', '277', '277 24', '139 24', '139 277 24', '139 277', '139', '136 24',
    '136 277 24', '136 277', '136', '136 139 24', '136 139 277 24', '136 139 277',
    '136 139', '246']

def find_supersets(strings):
    superstrings = set()
    set_to_string = dict(zip([frozenset(s.split()) for s in strings], strings))
    for s in set_to_string.keys():
        for sup in superstrings.copy():
            if s <= sup:
                # print('{s!r} <= {sup!r}'.format(s = s, sup = sup))
                break
            elif sup < s:
                # print('{sup!r} <= {s!r}'.format(s = s, sup = sup))
                superstrings.remove(sup)
        else:
            superstrings.add(s)
    return [set_to_string[sup] for sup in superstrings]

print(find_supersets(strings))

収量

['136 139 277 24', '246']

これは、文字列を事前にソートするよりも高速であることがわかります。

def using_sorted(strings):
    stsets = sorted(
        (frozenset(s.split()) for s in strings), key=len, reverse=True)
    superstrings = set()
    for stset in stsets:
        if not any(stset.issubset(s) for s in superstrings):
            superstrings.add(stset)
    return superstrings

In [29]: timeit find_supersets(strings)
100000 loops, best of 3: 18.3 us per loop
In [25]: timeit using_sorted(strings)
10000 loops, best of 3: 24.9 us per loop
于 2013-01-16T17:10:07.653 に答える
0

文字列が「strings」というリストにあると仮定します。

stset_string = {frozenset(s.split()):s for s in strings}
stsets = sorted(stset_string, key=len, reverse=True)
superstsets = set()
for stset in stsets:
    if not any(stset.issubset(s) for s in superstsets):
        superstsets.add(stset)
superstrings = [stset_string[s] for s in superstsets]

これにより、文字列内のトークンのセットを元の文字列にマッピングする辞書が作成され、スーパーストリングに対応するトークンのセットが決定され、元の文字列が検索されます。同じトークンを生成する複数の異なる文字列がある場合、任意の文字列がスーパー文字列を定義するものと見なされることに注意してください。これを変更して、たとえばスーパーストリングのすべての可能なセットを取得することができます。

于 2013-01-16T16:53:55.313 に答える