如何使用排列生成字典的键

Question

我需要创建一个字典，值可以保留为空或零，但是我需要键是所有可能的字符组合，例如k=8

lex = defaultdict(int)     
lex = {
'AAAAAAAA':0,
'AAAAAAAB':0,
'AAAAAABB':0,
...}

到目前为止，我尝试过这样的想法，我知道这是错误的，但我不知道如何让它工作，我是新的python，所以请忍受我。在

^{pr2}$

Answer 1

您可以在一行中完成，但您要查找的是combinations_with_replacement

from itertools import combinations_with_replacement
mydict = {"".join(key):0 for key in combinations_with_replacement('ACTG', 8)}

Answer 2

你所描述的不是排列，而是替换的组合。在itertools模块中也有一个函数。在

但是请注意，这里有6万个组合。试图把它们都放在字典里，甚至只是重复它们，都不会产生令人满意的结果。在

你的用例是什么？您可能只需要识别组合，而不是完全生成它们。每一个组合都与一个特定的16位整数索引相关联，因此您可以对其进行存储和操作。在

Answer 3

虽然组合使用_with_replacement功能非常好，但是您将生成一个具有相对较高冲突率（约20%）的字符串的巨大列表

你要做的事情可以用base4整数来完成。它们不仅处理速度更快，内存效率更高，而且还有0冲突（每个数字都是自己的哈希值），这意味着在最坏的情况下有保证的O（1）查找时间。在

def num_to_hash(n, k, literals='ABCD'):
    return ''.join((literals[(n >> (k - x)*2 & 3)] for x in xrange(1, k+1)))

k = 2
d = {num_to_hash(x, k, 'ACTG'): 0 for x in xrange((4**k) - 1)}
print d 

输出：

^{pr2}$