Find all list permutations of a string in Python
Question: I have a string of letters that I'd like to split into all possible
combinations (the order of letters must be remain fixed), so that:

    
    
    s = 'monkey'
    

becomes:

    
    
    combinations = [['m', 'onkey'], ['mo', 'nkey'], ['m', 'o', 'nkey'] ... etc]
    

Any ideas?


Answer: <http://wordaligned.org/articles/partitioning-with-python> contains an
interesting post about sequence partitioning, here is the implementation they
use:

    
    
    #!/usr/bin/env python
    
    # From http://wordaligned.org/articles/partitioning-with-python
    
    from itertools import chain, combinations
    
    def sliceable(xs):
        '''Return a sliceable version of the iterable xs.'''
        try:
            xs[:0]
            return xs
        except TypeError:
            return tuple(xs)
    
    def partition(iterable):
        s = sliceable(iterable)
        n = len(s)
        b, mid, e = [0], list(range(1, n)), [n]
        getslice = s.__getitem__
        splits = (d for i in range(n) for d in combinations(mid, i))
        return [[s[sl] for sl in map(slice, chain(b, d), chain(d, e))]
                for d in splits]
    
    if __name__ == '__main__':
        s = "monkey"
        for i in partition(s):
            print i
    

Which would print:

    
    
    ['monkey']
    ['m', 'onkey']
    ['mo', 'nkey']
    ['mon', 'key']
    ['monk', 'ey']
    ['monke', 'y']
    ['m', 'o', 'nkey']
    ['m', 'on', 'key']
    ['m', 'onk', 'ey']
    ['m', 'onke', 'y']
    ['mo', 'n', 'key']
    ['mo', 'nk', 'ey']
    ['mo', 'nke', 'y']
    ['mon', 'k', 'ey']
    ['mon', 'ke', 'y']
    ['monk', 'e', 'y']
    ...
    ['mo', 'n', 'k', 'e', 'y']
    ['m', 'o', 'n', 'k', 'e', 'y']
    

