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
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'])]

freezesets 的原因很快就会显现出来。我将在下面解释原因。我们想要集合的原因是因为它有一个方便的超集比较运算符：

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

假设您的字符串在一个名为“字符串”的列表中：

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 回答