组合算法

有A，T，C，G四个字符串，一共有6个位置，每个位置可以填四个中的任意一个，输出所有的组合。
1，递归输出。

def permutations(n,s=''):
    if(n==0):
        print(s)
    else:
        permutations(n-1,s+"A")
        permutations(n-1,s+"T")
        permutations(n-1,s+"C")
        permutations(n-1,s+"G")

permutations(6)即可调用。
2,利用itertools。

>>> from itertools import combinations, permutations
>>> combinations([1,2,3,4,5],2)
<itertools.combinations object at 0x10469a650>
>>> [i for i in combinations([1,2,3,4,5],2)]
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
>>> [i for i in permutations([1,2,3,4,5],2)]
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)]

>>> from itertools import combinations, permutations
>>> [i for i in permutations(['A','T','C','G'],4)]
[('A', 'T', 'C', 'G'), ('A', 'T', 'G', 'C'), ('A', 'C', 'T', 'G'), ('A', 'C', 'G', 'T'), ('A', 'G', 'T', 'C'), ('A', 'G', 'C', 'T'), ('T', 'A', 'C', 'G'), ('T', 'A', 'G', 'C'), ('T', 'C', 'A', 'G'), ('T', 'C', 'G', 'A'), ('T', 'G', 'A', 'C'), ('T', 'G', 'C', 'A'), ('C', 'A', 'T', 'G'), ('C', 'A', 'G', 'T'), ('C', 'T', 'A', 'G'), ('C', 'T', 'G', 'A'), ('C', 'G', 'A', 'T'), ('C', 'G', 'T', 'A'), ('G', 'A', 'T', 'C'), ('G', 'A', 'C', 'T'), ('G', 'T', 'A', 'C'), ('G', 'T', 'C', 'A'), ('G', 'C', 'A', 'T'), ('G', 'C', 'T', 'A')]

3，变化进制加法实现。
比如，求10位每位上有两种选择，0或1,的所有排列组合，这个时候我们只需遍历一遍0到1024(2的10次方),0,1,10,11,100,......。再在前面补充0使字符串的总长度为10，是不是就可以得倒所有的排列组合了吗？
和这一道题同理，只不过这道题是4进制（0，1，2，3分别代表ATCG）。

def Permutations(max_len):
    singles=['A','T','C','C']
    dec=len(singles)
    def translate(n,dec=4):#这个函数是把10进制的数n补成dec=4进制，然后返回和singles对应索引的数反转后的字符串。
        a=[]
        while(True):
            a.append(n%dec)
            n=int(n/dec)
            if(n==0):
                break
        return "".join(map(lambda x:singles[x],a))[::-1]
    def supplement(s,max_len,default='A'):#这个函数在前面补充字符串为A（0）。
        return (max_len-len(s))*'A'+s
    for i in range(dec**max_len):
        print(supplement(translate(i,dec=dec),max_len=max_len))

其中，数组singles为每个位置可以放的字符串集合，max_len为字符串的位数。
Permutations(6)即可调用。