8
\$\begingroup\$

I am given a task to create a function that prints a random anagram of a given string:

def anagram(value):
    '''Prints random anagram of given value'''
    import random
    newWord = ''
    for i in range(len(value)):
        pos = random.randint(0, len(value)-1)
        newWord += value[pos]
        value = value[:pos] + value[pos+1:]
    print newWord


anagram('12345')
anagram('should')

What all edge cases should this program cover?

\$\endgroup\$
  • \$\begingroup\$ Possible duplicate of Simple anagram or permutation generator in Python \$\endgroup\$ – hjpotter92 Jan 17 '18 at 16:47
  • 3
    \$\begingroup\$ @hjpotter92 Asking for a code review of code that solves the same problem as in some other question is fine here. Just having copy & pasted the other persons code would be a dupe (and also off-topic), or re-posting your own question (without having changed anything), instead of editing it. \$\endgroup\$ – Graipher Jan 17 '18 at 16:54
  • 1
    \$\begingroup\$ Is is acceptable to return the input string? \$\endgroup\$ – Eric Duminil Jan 17 '18 at 20:37
6
\$\begingroup\$

You should usually not put the imports into your functions. While Python does not re-import a module it has already imported, it still needs to run the check for this. So this introduces an unnecessary overhead, when running the function multiple times. There are a few use cases for doing this, though, like not wanting to pollute the global namespace if that module does some dirty hacks during its initialization or it takes a very long time to import and you only want to do this sometimes (and only run the function once). But random is no such module.


Your code makes this also too complicated. The biggest part of your algorithm is making sure that you don't re-use a letter you already used. You can use random.sample for this, instead. It randomly samples (duh) from an iterable (well it needs to be iterable and indexable, actually), without replacement:

import random

def anagram(value):
    '''Returns random anagram of given value'''
    return ''.join(random.sample(value, len(value)))

An alternative would be random.shuffle, which shuffles a list in place, but this has the overhead of casting to a list first. The documentation actually recommends using the first one (which is also a lot clearer IMO).

def anagram(value):
    '''Returns random anagram of given value'''
   value_list = list(value)
   random.shuffle(value_list)
   return ''.join(value_list)

As for corner cases to test? The obvious one is the empty string ''. Then maybe a string containing only one distinct letter, like 'aaa' (to catch some very weird algorithm that only looks at the set of letters, which would be quite wrong, of course). And then finally maybe the scaling behavior of the algorithm so strings of increasing length.

All should be tested for example with this:

from collections import Counter

def test_anagram_function(s):
    assert Counter(s) == Counter(anagram(s))
\$\endgroup\$
11
\$\begingroup\$
  • When building a string you should build a list, and then use ''.join(). This is as strings are immutable, and so generating newWord takes \$O(n^2)\$ time.
  • You are mannually poping pos from value. If you change value to a list, you can just use list.pop.
  • You should import random at the top of your code. Never in a function.
  • Common Python style is to use snake_case for variables.
  • Common Python style is to use _ as a throw away variable.
  • You can use random.randrange, rather than randint
  • It's best if you return rather than print your anagram.

And so you could use:

def anagram(value):
    new_word = []
    value = list(value)
    for _ in range(len(value)):
        pos = random.randrange(len(value))
        new_word.append(value.pop(pos))
    return ''.join(new_word)

This however runs in \$O(n^2)\$ time. If you use a Fisher–Yates shuffle, you can do this in \$O(n)\$ time.

def anagram(value):
    value = list(value)
    for i in range(len(value)):
        pos = random.randrange(i, len(value))
        value[i], value[pos] = value[pos], value[i]
    return ''.join(value)

You can also use random.shuffle, which likely also uses the above algorithm. However you won't have to maintain it. Allowing:

def anagram(value):
    value = list(value)
    random.shuffle(value)
    return ''.join(value)
\$\endgroup\$
  • \$\begingroup\$ never” is a strong word. Sometimes, due to circular imports, you don’t have any other alternative:P (but of course it doesn’t apply in this scenario) \$\endgroup\$ – Grajdeanu Alex. Jan 17 '18 at 17:53
  • 4
    \$\begingroup\$ @MrGrj if you have circular imports you have much bigger problems than where your imports go. \$\endgroup\$ – Peilonrayz Jan 17 '18 at 17:55
  • \$\begingroup\$ Just curious : why "never in a function"? It could make sense for a heavy_computation() function, which uses many libraries but whose result gets cached for later use. \$\endgroup\$ – Eric Duminil Jan 17 '18 at 20:36
  • 2
    \$\begingroup\$ @EricDuminil The simple answer is PEP 8 says so. However, why wouldn't you make it a module? You can have it so it only loads when you do import module.submodule, just like a lot of the math and game libraries do. This has the benefit that it's cached without you having to do anything too. \$\endgroup\$ – Peilonrayz Jan 17 '18 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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