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?

• hjpotter92: Possible duplicate of Simple anagram or permutation generator in Python
• Graipher: @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.
• Eric Duminil: Is is acceptable to return the input string?

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

• Richard Neumann: well it needs to be iterable and indexable, actually - it's called a sequence ;-)

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)

• Grajdeanu Alex: "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)
• Peilonrayz: @MrGrj if you have circular imports you have much bigger problems than where your imports go.
• Eric Duminil: 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.
• Peilonrayz: @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.