python - 在 python 中的一组字符串中查找超字符串

Question

给定一组包含数字的字符串，我如何找到那些是超集的字符串。例如，如果出现字符串“139 24”和“139 277 24”，那么我想保留“139 277 24”，因为可以在其中找到“139 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

Answer 1

让我们列出这个问题的主要参与者:

• 字符串，例如'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'])]

frozensets 的原因很快就会明了。我将在下面解释原因。我们之所以需要集合，是因为它有一个方便的超集比较运算符:

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 ，我们将添加新的 superstrings如果它们不是已经存在的项目的子集 superstrings .

• 对于每个 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 是，所以有可能有一组 卡住集。这就是我们转换 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