Print a random anagram of a given string

Question

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?

Answer 1

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 a sequence (anything iterable and indexable) 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))

Answer 2

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