在Python中查找字符串集合中的超级字符串

Question

在Python中查找字符串集合中的超级字符串

5

给定一组包含数字的字符串，如何找到其中的超集。例如，如果出现字符串“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

- user1140126

1

@PenguinCoder，有没有办法证明这不是一份作业？ - user1140126

1

@user1140126，请发布您用来解决这个问题的代码。 - Ashwini Chaudhary

1

@PenguinCoder 作为一个社区，我们已经解决了“作业”问题：http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated。我们会提供帮助——无论是不是作业——因为这就是 SO 的宗旨。 - hexparrot

@hexparrot社区可以决定是否提供帮助。但是考虑到这个问题的第一个修订版本，FAQ似乎适用。user1140126已经发布了他的代码，而不仅仅是试图请求他人的代码。 - PenguinCoder

2

@hexparrot 很好的解释。感谢您礼貌的澄清。 - PenguinCoder

显示剩余2条评论

2个回答

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]

这将创建一个字典，将字符串中的令牌集映射到原始字符串，确定哪些令牌集对应于您的超级字符串，然后查找原始字符串。请注意，如果有多个不同的字符串产生相同的令牌，则将任意字符串作为定义超级字符串；您可能需要修改此设置以获取所有可能的超级字符串集。

- Michael J. Barber

谢谢，我正在获得超级字符串将 [frozenset（['24'，'139'，'136'，'277']），frozenset（['246']）] 作为结果，这是正确的，但是我需要维护每个超集中数字的顺序。稍后我会连接单个元素以恢复原始字符串“136 139 277 24”和“246”。 - user1140126

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- unutbu · Accepted Answer

让我们罗列一下这个问题中的主要因素：

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

很快你就会明白为什么要使用frozenset。我将在下面解释原因。我们想使用集合的原因是它们有一个方便的超集比较运算符：

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中的某个项目的子集，则将新的s添加到superstrings中。
对于每个s，遍历superstrings集合：for sup in superstrings。

检查s <= sup——也就是说，如果s是sup的子集，则退出循环，因为s比某个已知超级字符串更小。
检查sup <= s ——也就是说，如果s是superstrings中某个项目的超集。在这种情况下，删除superstrings中的该项目，并替换为s。

技术说明：

Because we are removing items from superstrings, we can not also iterate over superstrings itself. So, instead, iterate over a copy:
```
for sup in superstrings.copy():
```
And finally, we would like superstrings to be a set of sets. But the items in a set have to be hashable, and sets themselves are not hashable. But frozensets are, so it is possible to have a set of frozensets. This is why we converted strings into a list of 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