在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- 也就是说,if s是否为子集sup,退出循环,因为s它小于某个已知超级字符串.

  • 检查sup <= s- 是否- 如果 s是某个项目的超集superstrings.在这种情况下,请删除该项目superstrings并将其替换为s.

技术说明:

• 因为我们正在删除项目superstrings,所以我们也不能迭代superstrings自己.所以,相反,迭代一个副本:

  for sup in superstrings.copy():
  

• 最后,我们希望superstrings成为一组.但是一组中的项目必须是可清洗的,并且设置本身不可清除.但是冻结了,所以有可能有一套冷冻器.这就是我们转换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