1
\$\begingroup\$

Problem : Given a list of strings, some of which may be anagrams amongst themselves, print the permutations which can be so constructed so that each permutation has set of strings which is completely unique.

input : “asda”, “daas”, “dand”, “nadd”

output :  {“asda”, “dand”}, {“daas”, “dand”}, {“asda”, “nadd”}, {“daas”, “nadd”}

input : “laptop”, “toplap”, “loptap”, “mouse”

output :  {“laptop”, “mouse”}, {“toplap”, “mouse”}, {“loptap”, “mouse”}

Code :

def is_anagram(value_1, value_2):
    """checks whether the two given strings are anagrams """
    if sorted(value_1) == sorted(value_2):
        return True

def random_set(input_value):
    """returns the set of strings which are completely unique"""
    if len(input_value) <= 2:
        output = input_value
    else:
        output = []
        for i in range(len(input_value)):
            for j in range(len(input_value)):
                if not is_anagram(input_value[i], input_value[j]):
                    output.append( {input_value[i], input_value[j]})

    return output

print random_set(["asda", "daas" , "dand" , "nadd"])
print random_set(["laptop", "toplap", "loptap", "mouse"])

Though the code gives the correct output but it makes duplicate copy of the sets. How can i remove this flaw?

\$\endgroup\$
2
  • \$\begingroup\$ I'm assuming this is Python 2? \$\endgroup\$
    – Mast
    Jan 22, 2018 at 17:27
  • \$\begingroup\$ yes it's Python2.7. \$\endgroup\$ Jan 22, 2018 at 17:38

4 Answers 4

2
\$\begingroup\$

The time complexity of your is_anagram function is \$\mathcal{O}(n\log n)\$, because of the sorting. Instead you could get by with this simple \$\mathcal{O}(n)\$ function, using collections.Counter, which just counts the number of appearances of each letter/symbol. You should also directly return the result of the comparison (again).

from collections import Counter

def is_anagram(value_1, value_2):
    """checks whether the two given strings are anagrams """
    return Counter(value_1) == Counter(value_2)

For your actual function, you should use itertools.product:

import itertools

def random_set(input_value):
    """returns the set of strings which are completely unique"""
    if len(input_value) <= 2:
        return input_value

    for x, y in itertools.product(input_value, input_value):
        if not is_anagram(x, y):
            yield {x, y}

This is now a generator that yields the tuple. You can call list or set on it to get all its values. Alternatively you could return the whole list using a list comprehension:

def random_set(input_value):
    """returns the set of strings which are completely unique"""
    if len(input_value) <= 2:
        return input_value

    return [{x, y}
            for x, y in itertools.product(input_value, input_value)
            if not is_anagram(x, y)]

Or better yet, return a set of frozensets (because you can not have a set of sets, since a set is not hashable):

def random_set(input_value):
    """returns the set of strings which are completely unique"""
    if len(input_value) <= 2:
        return input_value

    return {frozenset([x, y])
            for x, y in itertools.product(input_value, input_value)
            if not is_anagram(x, y)}
\$\endgroup\$
3
\$\begingroup\$

I don't think your current algorithm is that good.

  1. You loop through all input_values twice, not even removing clearly know duplicates.

    If you instead used say a half_product function, then you'd remove a lot of checks. This is as you know if you've already visited the value with i, then you won't need to visit again with j.

    This is as set('ab') == set('ba').

  2. You can group the anagrams, to reduce the code complexity.

    Currently you have two \$O(n)\$ loops - running in \$O(n^2)\$ time - where \$n\$ is the size of input_values. After this, you then run in \$O(v\log{v})\$ - where \$v\$ is the max size of the values. And so is \$O(n^2 v\log{v})\$.

    However you can group all the values in \$O(n v\log{v})\$ time. This means you now have \$g\$ groups, of \$a\$ anagrams. Being roughly \$ag = n\$. From this you have to loop all groups and anagrams leaving \$O(g^2 a^2)\$ time. And so is \$O(n v\log{v} + g^2 a^2)\$. Which is better in all cases, except where \$g\$ or \$a\$ are \$1\$.

And so I'd use:

def half_product(it):
    it = list(it)
    for i, value in enumerate(it):
        for j in range(i+1, len(it)):
            yield value, it[j]

def random_set(values):
    d = {}
    for value in values:
        d.setdefault(tuple(sorted(value)), set()).add(value)

    for anagrams in half_product(d.values()):
        yield from itertools.product(*anagrams)
\$\endgroup\$
2
\$\begingroup\$

You can't directly throw the result of random_set into a set to find the unique elements because a set is not hash-able. So if you convert each set in the list to a tuple first then throw them all in a set it should do what you want.

result = set(tuple(y) for y in random_set(["laptop", "toplap", "loptap", "mouse"]))

And if you really need the containers to be a list of sets then

[ set(x) for x in result ]

List comprehensions and generators are your friend my friend.

\$\endgroup\$
3
  • \$\begingroup\$ The bitter sweet tang of built in collections. It would be nice if python collections were implemented in such a way that you could replace them with your own implementations, such as a hashable set, while still retaining the literal syntax and comprehensions. This is definitely an area where Scala and C# far outstrip the capabilities of Python in the space of mainstream languages. \$\endgroup\$ Jan 22, 2018 at 18:39
  • 1
    \$\begingroup\$ @AluanHaddad If you need a hashable set, you can use frozenset. It supports generator expressions (so frozenset(x for x in range(10))). Of course it is not mutable anymore. \$\endgroup\$
    – Graipher
    Jan 22, 2018 at 21:41
  • 1
    \$\begingroup\$ @Graipher that's nice, I didn't know that. I still would prefer a patterns over methods approach so that I could plug in arbitrary monads like in Scala or C# comprehensions though. \$\endgroup\$ Jan 22, 2018 at 22:35
1
\$\begingroup\$

Problem : Given a list of strings, some of which may be anagrams amongst themselves, print the permutations which can be so constructed so that each permutation has set of strings which is completely unique.

This is an atrocious spec. IMO you needed to spend more time on requirements gathering before starting to code. As it is, we're forced to try to reverse engineer the requirements from two test cases.

input : “asda”, “daas”, “dand”, “nadd”

output :  {“asda”, “dand”}, {“daas”, “dand”}, {“asda”, “nadd”}, {“daas”, “nadd”}

Since {"asda", "dand"} is included in the output but {"dand", "asda"} is not, clearly permutation is the wrong word.

As for "uniqueness", it appears from the examples that what this really means is that none of the output sets should contain two words which are anagrams of each other.

Finally, I note that all of the output sets are maximal under that assumption, although nothing in the problem statement hints at that.

So the real requirements seem to be

Given a list of strings, some of which may be anagrams of each other, output a list containing every maximal subset which doesn't contain two words which are anagrams of each other.


Other answers have already commented on is_anagram, and I have nothing to add.

def random_set(input_value):

That's a misleading name: it strongly implies that the return value is a single set, whereas in fact it should be a list of sets.

    """returns the set of strings which are completely unique"""

No, it doesn't. If it did, the implementation would be just return set(input_value).

    if len(input_value) <= 2:
        output = input_value

I don't believe that Python style guides prohibit early returns, and it's easier to understand what an early return is doing than an assignment to a variable which then isn't used again for a long time.

Also, this is buggy. Consider the test case ["asda", "daas"], which should return [{"asda"}, {"daas"}].

In fact, it should be obvious that it's wrong because it doesn't return the same type as the else case. One branch returns a list of strings, and the other a list of sets of strings.

    else:
        output = []
        for i in range(len(input_value)):
            for j in range(len(input_value)):
                if not is_anagram(input_value[i], input_value[j]):
                    output.append( {input_value[i], input_value[j]})

You seem to have reverse engineered a very different spec to me. I'm pretty sure that there are inputs for which the subsets should have more than two elements.

If my understanding of the spec is correct, there should be a phase which gathers the input strings into equivalence classes and then another phase which calculates a Cartesian product of all of the equivalence classes.

\$\endgroup\$

Your Answer

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

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