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

我需要创建一个字典，值可以留空或零，但我需要的键是ABCD字符与长度k的所有可能的组合。例如，对于k = 8如何使用排列生成字典的键

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

所以这样到目前为止，我已经尝试somethink，我知道这是错误的，但我不知道如何使它工作，我在蟒蛇很新，所以请多多包涵。

mydiction = {} 
mylist = [] 
mylist = itertools.permutations('ACTG', 8) 
for keys in mydiction: 
    mydiction[keys] = mylist.next() 
print(mydiction)

来源

2013-11-15 Karapapas

是 'AAAB' 和 'BAAA' 等效？ –

你能做到在同一行，但你正在寻找的是combinations_with_replacement

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

来源

2013-11-15 12:27:11 thefourtheye

你可以在这里使用'dict.fromkeys（iterable，0）'而不是dict-comp –

@JonClements但是必须加入密钥。那从'fromKeys'不可能吧？ – thefourtheye

报废 - 在输入一个gen-exp之后，你无论如何都得不到任何东西...... :) –

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

但是，请注意，那里有六万个组合。试图把它们全部写入字典，甚至只是遍历它们，都不会产生令人满意的结果。

你的用例是什么？你可能只需要识别组合，而不是全部生成它们。每个组合都与一个特定的16位整数索引有内在联系，所以你可以改为存储和操作它。

来源

2013-11-15 12:31:06 Sneftel

我知道玩这样的数字并不是最好的做法，我知道有更好的解决方案，我试图做的，只是让算法更优雅是一个更复杂的任务。这就是为什么我需要用这个“蛮力”方法来完成这部分工作，在得到我的结果后，我会尽力完善它。 – Karapapas

虽然combinations_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

输出：

{'AA': 0, 
'AC': 0, 
'AG': 0, 
'AT': 0, 
'CA': 0, 
'CC': 0, 
'CG': 0, 
'CT': 0, 
'GA': 0, 
'GC': 0, 
'GT': 0, 
'TA': 0, 
'TC': 0, 
'TG': 0, 
'TT': 0}

来源

2013-11-15 12:57:21

这不会生成替换组合，但会生成笛卡尔产品。我不确定是否购买了您的碰撞率：对于我来说，即使使用20个字符的密钥，我也会得到852610和852529独特哈希值的字典大小，因此碰撞率可以忽略不计。（我认为无论如何都担心它会很愚蠢，但我无法追踪你的数字来自哪里。） – DSM

实际验证并不难，创建一个这样的字符串列表，创建一个由哈希组成的列表的每一个元素，并把它变成一个集合。集合和列表之间的长度差异等于碰撞次数。当然这不是问题，串哈希已知有很好的性能。20％的数字仅使用8个字符长度的字符串。当然需要进行更深入的分析，我相信对整体性能的影响可能很小，但它仅仅意味着它不是最好的解决方案:) 这是由于少量的文字。 –

但这就是我得到上述数字的地方。对于一个8字符的字符串，我根本没有发生散列冲突。如果碰到<= 65536个字符串时发生了20％的冲突，则有些错误。 – DSM

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

回答

相关问题