#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
Word Permutations
~~~~~~~~~~~~~~~~~

Generate all possible word permutations.

I used this to aid in solving some puzzles.

Note that a word of ``n`` characters results in ``n!`` permutations.  However,
duplicates are removed.

For some possible factorial function implementations, see the `factorial
recipe`_ at the `ASPN Python Cookbook`_.

.. _factorial recipe:     http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/67668
.. _ASPN Python Cookbook: http://aspn.activestate.com/ASPN/Cookbook/Python

:Copyright: 2005-2008 Jochen Kupperschmidt
:Date: 26-Apr-2008
:License: MIT
"""

from os.path import basename
from sys import argv, exit


def main(word):
    print 'Reordering: ' + word
    chars = list(word)
    chars.sort()
    print 'Chars: %s (%d)' % (''.join(chars), len(chars))
    words = swap(chars)
    # Filter duplicates and sort.
    words = sorted(set(words))
    for word in words:
        print word

def swap(remaining, ordered=[]):
    """Recursively swap characters."""
    for i in xrange(len(remaining)):
        remaining2 = remaining[:]
        ordered2 = ordered + [remaining2.pop(i)]
        if len(remaining2) > 0:
            for word in swap(remaining2, ordered2):
                yield word
        else:
            yield ''.join(ordered2)

if __name__ == '__main__':
    if len(argv) != 2:
        print 'Usage: %s <word>' % basename(argv[0])
        exit(2)
    main(argv[1])