Python排列组合问题

浏览数：83 / 时间：2015年06月08日

1.字符串的全排列

问题描述：打印出原字符串中所有字符的所有排列。——将输入字符串中的每个字符作为一个不同的字符看待，即使它们是重复的，如‘aaa‘应打印6次。

Python可以用生成器解决：

def permutation(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in permutation(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]

if __name__ == "__main__":
    s=‘Diei‘
    for item in list(permutation(list(s))):
        print ‘‘.join(item)

——生成器方法就是不停的插入前面一个元素的过程。

2.字符串的全组合

问题描述：打印出原字符串中所有字符的所有可能的组合。组合长度范围在1到字符串长度之间。

import copy

def combine(l, n):
    if n==0:
        return
    answers = []
    one = [0 for i in range(n)]
    def next_c(li = 0, ni = 0): 
        if ni == n:
            answers.append(copy.copy(one))
            return
        for lj in xrange(li, len(l)):
            one[ni] = l[lj]
            next_c(lj + 1, ni + 1)
    next_c()
    return answers

if __name__ == "__main__":
    s=‘Dieicd‘
    l=list(set(s))
    answer=[]
    for i in range(len(l)):
        answer+=combine(l,i+1)
    print len(answer)
    for i in answer:
        print ‘‘.join(i)

——按包含的字符来检测

3.使用Python的itertools库

from itertools import product
#两个序列对应的排列
from itertools import permutations
#排列
from itertools import combinations
#组合
l = [1, 2, 3]
print len(list(product(l,repeat=3)))
#print list(product(l, repeat=4))
print list(permutations(l))    
print list(combinations([1,2,3,4,5], 3))