Print all permutations from a given list of strings such that each set of strings is completely unique

Question

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?

Answer 1

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

Answer 2

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)

Answer 3

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.

Answer 4

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.