5

Given a set strings of containing numbers, how can I find those strings that are the superset. For example if strings '139 24' and '139 277 24' appear then I want to keep '139 277 24' as '139 24' can be found inside it. Also these numbers may appear in any order inside a string.

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

The result for the above data is given below.

   '136 139 277 24'
              '246'

Edit: I am splitting each string and putting individual numbers in a set and then comparing this through the sets created from the whole list. I can find a solution using this approach but I think there should be some other elegant way to perform the same.

I was trying the following code and felt that it is becoming unnecessarily complex.

#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
7
  • 1
    @PenguinCoder, Is there a way to prove that this is not a homework? Commented Jan 16, 2013 at 16:37
  • 1
    @user1140126 post the code you used to solve this. Commented Jan 16, 2013 at 16:38
  • 1
    @PenguinCoder As a community, we have settled the 'homework' concern : meta.stackexchange.com/questions/147100/… We help--regardless of whether it is homework--because that is what SO is for.
    – hexparrot
    Commented Jan 16, 2013 at 16:53
  • Try using the set.issuperset(other) method which can also be written as a logical expression set >= other.
    – martineau
    Commented Jan 16, 2013 at 16:54
  • 2
    @hexparrot Good explanation. Thanks for the polite clarification. Commented Jan 16, 2013 at 17:53

2 Answers 2

8

Let's make a laundry list of the major players in this problem:

  • strings, e.g. '24 139 277'
  • sets -- a collection of "superstrings"
  • superset inclusion -- the <= set operator
  • splitting the strings into a set of number-strings: e.g. set(['24', '139', '277'])

We are given a list of strings, but what we'd really like -- what would be more useful -- is a list of sets:

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

The reason for frozensets will become apparent shortly. I'll explain why, below. The reason why we want sets at all is because that have a convenient superset comparison operator:

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

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

This is exactly what we need to determine if one string is a superstring of another.

So, basically, we want to:

  • Start with an empty set of superstrings = set()
  • Iterate through strings: for s in strings.
  • As we examine each s in strings, we will add new ones to superstrings if they are not a subset of a item already in superstrings.
  • For each s, iterate through a set of superstrings: for sup in superstrings.

    • Check if s <= sup -- that is, if s is a subset of sup, quit the loop since s is smaller than some known superstring.

    • Check if sup <= s -- that is, if s a superset of some item in superstrings. In this case, remove the item in superstrings and replace it with s.

Technical notes:

  • 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))

yields

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

It turns out this is faster than pre-sorting the strings:

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
3
  • Since the OP apparently wants the strings and not the sets anyway, something like to_sets = {k: set(k.split()) for k in s}; superstrings = {k for k,v in to_sets.iteritems() if not any(other > v for other in to_sets.itervalues())} might work too. [The performance wouldn't be great, of course.]
    – DSM
    Commented Jan 16, 2013 at 17:24
  • Thanks for such a detailed description, however the problem of getting the superstrings back is not solved. We can't reconstruct the original string from the output. Commented Jan 16, 2013 at 17:26
  • @user1140126: I've modified find_supersets to remember the original string. The dict set_to_string maps from frozensets back to the original string.
    – unutbu
    Commented Jan 16, 2013 at 17:33
0

Assuming your strings are in a list called "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]

This creates a dictionary mapping sets of the tokens in the strings to the original strings, determines which of the sets of tokens correspond to your superstrings, then looks up the original strings. Note that, if there are multiple different strings producing the same tokens, an arbitrary string will be taken as defining the superstring; you may want to modify this to get, e.g., all possible sets of superstrings.

1
  • Thanks, I am getting >>> superstrings set([frozenset(['24', '139', '136', '277']), frozenset(['246'])]) as result which is correct however, I need to maintain the ordering of numbers in each superset. I will later join the individual elements to get back the original string '136 139 277 24' and '246'. Commented Jan 16, 2013 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.