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

Question

我有一串字母，我想分成所有可能的组合（字母顺序必须保持固定），使：

s = 'monkey' 

变成：

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

任何想法？

Answer 1

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 2

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 3

的想法是要认识到的该排列字符串s等于包含s本身的集合，以及s的每个子字符串X与集合的集合并集s\X。例如，permute('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

的字符串（而不是列出）取向的方法是认为每对相邻字符中的由任一分离空间或空字符串。这可以被映射到1和0，以及可能的分割数是2的幂：

2 ^（LEN（S）-1）

例如， “密钥” 可以具有 '' 或“”分离“科”和'或“”分离“EY”这导致4种可能性：

• 键（“的” e“之间”“K”和“E”，“”和'之间Y '）
• ķEY（' 的 'e '之间 ' 'K' 和 'E'，'' 和 'y'）
• 密钥（' ' 'K' 和 'E'，''之间之间'e'和'y'）
• 柯Y（数 'k' 和 'E'， '' 'E' 之间和 'y' '之间'）

一个不可读蟒一个衬里，让你字符串形式的发电机：

operator_positions = (''.join([str(a >> i & 1).replace('0', '').replace('1', ' ') + s[len(s)-1-i] for i in range(len(s)-1, -1, -1)]) for a in range(pow(2, len(s)-1))) 

这个发生器的可读版本与评论和样品：

s = 'monkey' 
s_length = len(s)-1 # represents the number of ' ' or '' that can split digits 

operator_positions = (
    ''.join(
     [str(a >> i & 1).replace('0', '').replace('1', ' ') + s[s_length-i] 
     for i in range(s_length, -1, -1)]) # extra digit is for blank string to always precede first digit 
    for a in range(pow(2, s_length)) # binary number loop 
) 
for i in operator_positions: 
    print i 

STR（一个>> I & 1）转换一个成二进制串，然后有它的0和1的由“”取代和''，r espectively。二进制字符串是多余的数字，因此第一个数字总是“'。这样，由于数字分离器与第一个字符结合在一起，因此总是只产生第一个字符。