CODEWITHSUNDEEP
python
kiltannen
kiltannen

Reputation: 1137

Symmetric pairs from a list of words using python SET operations

I am trying to figure out a question from my class at school, and while I have got close the last bit of logic escapes me, this is the question we have been given:

The words parameter contains a list of two character words (lower case, no duplicates). Using sets, find an O(n) solution for displaying all symmetric pairs of words.

For example, if words was: [am, at, ma, if, fi], we would display:

am & ma

if & fi

The order of the display does not matter. 'at' would not be displayed because 'ta' is not in the list of words.

I have made some code that gets me daily close - I end up with what looks like a correct "set" that gives me the elements I need to turn into pairs.

def find_pairs(words):
    reverseWords = []   
    for i in words:
        reverseWords.append(i[::-1])
    s1 = set(words)
    # reverse the list
    s2 = set(reverseWords)
    s3= set()
    # do an intersection to find matching pairs
    s3 = s1.intersection(s2)

    # Display the 3 sets - original - reversed & set of what needs to be the pairs
    print (s1,s2,s3)  

find_pairs(["am","at","ma","if","fi"])      # ma & am, fi & if

The above code gives this result

{'am', 'ma', 'fi', 'at', 'if'} {'am', 'ma', 'fi', 'ta', 'if'} {'ma', 'if', 'am', 'fi'}

I can't figure out a bit of logic that will allow me to turn set3 into the symmetric pairs I need. Or at least - not using set operations. They also indicate we should try and do this in a fairly elegant fashion (I think) - by saying they want an O(n) solution. They've also pretty much said that converting everything to lists and doing it in that is not what they want. (That is what I tried to do & had some success, but then ran into my solution not using set operations...)

Any suggestions would be greatly appreciated.

Upvotes: 0

Views: 364

Answers (1)

Nelewout
Nelewout

Reputation: 6574

You can do this with less bookkeeping than the other answer by creating pairs in alphabetic order. E.g.:

def find_pairs(words):
    word_set = set(words)
    pairs = set()

    for word in words:
        rev = word[::-1]
        pair = (rev, word) if rev < word else (word, rev)

        if rev in word_set:  # sets don't take duplicates, so we do
            pairs.add(pair)  # not need an explicit check for pair

    return pairs

This is clearly in linear time, so it meets you requirements. I find:

>>>find_pairs(["am", "at", "ma", "if", "fi"])
{('am', 'ma'), ('fi', 'if')}

Upvotes: 1

Related Questions