查找在Python中拆分字符串的所有列表排列

Question

我有一串字母,我想分成所有可能的组合(字母的顺序必须保持固定),这样:

s = 'monkey'

变为:

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

有任何想法吗？

Answer 1

http://wordaligned.org/articles/partitioning-with-python包含一篇关于序列分区的有趣帖子,这里是他们使用的实现:

#!/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

哪个会打印:

['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']

Answer 2

def splitter(str):
    for i in range(1, len(str)):
        start = str[0:i]
        end = str[i:]
        yield (start, end)
        for split in splitter(end):
            result = [start]
            result.extend(split)
            yield result

combinations = list(splitter(str))

请注意,我默认使用生成器来避免长字符串内存不足.

Answer 3

这个想法是要认识到字符串的排列s等于包含s其自身的集合，以及 的每个子串与的排列X的集合并集。例如，：ss\Xpermute('key')

1. {'key'} # 'key' itself
2. {'k', 'ey'} # substring 'k' union 1st permutation of 'ey' = {'e, 'y'}
3. {'k', 'e', 'y'} # substring 'k' union 2nd permutation of 'ey' = {'ey'}
4. {'ke', 'y'} # substring 'ke' union 1st and only permutation of 'y' = {'y'}
5. 1、2、3 和 4 的并集产生字符串 的所有排列key。

考虑到这一点，可以实现一个简单的算法：

>>> def permute(s):
    result = [[s]]
    for i in range(1, len(s)):
        first = [s[:i]]
        rest = s[i:]
        for p in permute(rest):
            result.append(first + p)
    return result

>>> for p in permute('monkey'):
        print(p)    

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

Answer 4

考虑more_itertools.partitions：

给定

import more_itertools as mit


s = "monkey"

演示

按原样：

list(mit.partitions(s))
#[[['m', 'o', 'n', 'k', 'e', 'y']],
# [['m'], ['o', 'n', 'k', 'e', 'y']],
# [['m', 'o'], ['n', 'k', 'e', 'y']],
# [['m', 'o', 'n'], ['k', 'e', 'y']],
# [['m', 'o', 'n', 'k'], ['e', 'y']],
# [['m', 'o', 'n', 'k', 'e'], ['y']],
# ...]

经过一些字符串连接后：

[list(map("".join, x)) for x in mit.partitions(s)]

输出

[['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'],
 ['m', 'o', 'n', 'key'],
 ['m', 'o', 'nk', 'ey'],
 ['m', 'o', 'nke', 'y'],
 ['m', 'on', 'k', 'ey'],
 ['m', 'on', 'ke', 'y'],
 ['m', 'onk', 'e', 'y'],
 ['mo', 'n', 'k', 'ey'],
 ['mo', 'n', 'ke', 'y'],
 ['mo', 'nk', 'e', 'y'],
 ['mon', 'k', 'e', 'y'],
 ['m', 'o', 'n', 'k', 'ey'],
 ['m', 'o', 'n', 'ke', 'y'],
 ['m', 'o', 'nk', 'e', 'y'],
 ['m', 'on', 'k', 'e', 'y'],
 ['mo', 'n', 'k', 'e', 'y'],
 ['m', 'o', 'n', 'k', 'e', 'y']]

通过安装> pip install more_itertools。