Recursive Python function to produce a list of anagrams

Question

After a lot of head scratching and googling I still can't figure this out. I'm very new to Python and I'm struggling with the syntax. Conceptually I think I have a pretty decent idea of what I want to do and how to do so recursively. Technically however, coding it into Python however is proving to be a nightmare.

Basically I want to add all of the permutations of a word to list (no duplicate characters allowed), which can then be called by another program or function.

The return command and how to handle white space is really confusing me. I want the recursive function to "return" something once it unwinds but I don't want it to stop the function until all of the characters have iterated and all the permutations have been recursively generated within those iterations. When I run the code below nothing seems to happen.

def permutations(A, B = ''):
    assert len(A) >= 0
    assert len(A) == len(set(A))
    res = []
    if len(A) == 0: res = res.extend(B)
    else:
        for i in range(len(A)):
            permutations(A[0:i] + A[i+1:], B + A[i])
    return res

permutations('word'))

If I run the code below it prints out OK to my display pane, but I can't figure out how to get it into an output format that can be used by other program like a list.

def permutations(A, B = ''):
    assert len(A) >= 0
    assert len(A) == len(set(A))
    if len(A) == 0: print(B)
    else:
        for i in range(len(A)):
            permutations(A[0:i] + A[i+1:], B + A[i])

permutations('word')

Please could someone advise me on this, while I have some hair left! Very gratefully received.

Thank you

Jon

Answer 1

Basically your mistake is in

res = res.extend(B)

.extend() doesn't return a new list, but modifies the instance.

Another problem is that you don't use the return value from your recursive calls. Here is one way to fix your code:

def permutations(A, B = ''):
    assert len(A) >= 0
    assert len(A) == len(set(A))
    if len(A) == 0:
        return [B]
    else:
        res = []        
        for i in range(len(A)):
            res.extend(permutations(A[0:i] + A[i+1:], B + A[i]))

        return res

print permutations('word')

Answer 2

Like this?

from itertools import permutations
a = [x for x in permutations('word')]
print a

Output:

>>[('w', 'o', 'r', 'd'), ('w', 'o', 'd', 'r'), ('w', 'r', 'o', 'd'),
>>('w', 'r', 'd', 'o'), ('w', 'd', 'o', 'r'), ('w', 'd', 'r', 'o'), 
>>('o', 'w', 'r', 'd'), ..............

EDIT: I just realized you said no duplicate characters allowed. It does not really matter for 'word', but let's say you have 'wordwwwdd'. Then you could do:

[x for x in permutations(''.join(set('wordwwwdd')))] 

But it will mess up the order because of using set, so it will look like:

>> [('r', 'o', 'w', 'd'), ('r', 'o', 'd', 'w'), ('r', 'w', 'o', 'd')....

Answer 3

I would do it like this:

def permute_nondupe_letters_to_words(iterable):
    return (''.join(i) for i in itertools.permutations(set(iterable)))

And to use it:

word = 'word'
permutation_generator = permute_nondupe_letters_to_words(word)

bucket_1, bucket_2 = [], []
for i in permutation_generator:
    bucket_1.append(i)
    if i == 'owdr':
        break

for i in permutation_generator:
    bucket_2.append(i)

And

print(len(bucket_1), len(bucket_2))

prints:

(10, 14)

Answer 4

Here is another way to approach this problem:

• it is Python 2.7 and 3.3 compatible (have not yet tested with other versions)

• it will accept input containing duplicate items, and only return unique output (ie permutations("woozy") will only return "oowzy" once)

• it returns output in sorted order (and will allow you to specify sort key and ascending or descending order)

• it returns string output on string input

• it runs as a generator, ie does not store all combinations in memory. If that's what you want, you have to explicitly say so (example shown below)

• Edit: it occurred to me that I had omitted a length parameter, so I added one. You can now ask for things like all unique 4-letter permutations from a six-letter string.

Without further ado:

from collections import Counter
import sys

if sys.hexversion < 0x3000000:
    # Python 2.x
    dict_items_list = lambda d: d.items()
    is_string       = lambda s: isinstance(s, basestring)
    rng             = xrange
else:
    # Python 3.x
    dict_items_list = lambda d: list(d.items())
    is_string       = lambda s: isinstance(s, str)
    rng             = range

def permutations(lst, length=None, key=None, reverse=False):
    """
    Generate all unique permutations of lst in sorted order

        lst        list of items to permute
        length     number of items to pick for each permutation (defaults to all items)
        key        sort-key for items in lst
        reverse    sort in reverse order?
    """
    # this function is basically a shell, setting up the values
    # for _permutations, which actually does most of the work
    if length is None:
        length = len(lst)
    elif length < 1 or length > len(lst):
        return []     # no possible answers

    # 'woozy' => [('w', 1), ('o', 2), ('z', 1), ('y', 1)]  # unknown order
    items = dict_items_list(Counter(lst))
    # => [('o', 2), ('w', 1), ('y', 1), ('z', 1)]          # now in sorted order
    items.sort(key=key, reverse=reverse)

    if is_string(lst):
        # if input was string, return generator of string
        return (''.join(s) for s in _permutations(items, length))
    else:
        # return generator of list
        return _permutations(items, length)

def _permutations(items, length):
    if length == 1:
        for item,num in items:
            yield [item]
    else:
        for ndx in rng(len(items)):
            # pick an item to start with
            item, num = items[ndx]

            # make new list of remaining items
            if num == 1:
                remaining_items = items[:ndx] + items[ndx+1:]
            else:
                remaining_items = items[:ndx] + [(item, num-1)] + items[ndx+1:]

            # recurse against remaining items
            for perm in _permutations(remaining_items, length-1):
                yield [item]+perm

# test run!
words = list(permutations("woozy"))

results in

['oowyz',
 'oowzy',
 'ooywz',
 'ooyzw',
 'oozwy',
 'oozyw',
 'owoyz',
 # ...
 'zwooy',
 'zwoyo',
 'zwyoo',
 'zyoow',
 'zyowo',
 'zywoo']   # 60 items = 5!/2!, as expected