Python 从嵌套列表中最小数量的重复值创建列表

Question

我有一个字典

whs = {
    'ID1' : ['code1', 'code2', 'code3'],
    'ID2' : ['code2', 'code5', 'code3'],
    'ID3' : ['code6', 'code7', 'code8'],
    'ID4' : ['code3', 'code5', 'code6'],
}

我需要做的是建立一个看起来像这样的新列表

submit = [
    {
        'codes' : ['code3', ],
        'ids' : ['ID1', 'ID2', 'ID4'],
    },
    {
        'codes' : ['code6', 'code7', 'code8'],
        'ids' : ['ID3', ],
    }
]

到目前为止我所拥有的

def ParseAvailable(self, whs):
    separate = whs.keys()
    submit = []
    while len(separate) > 0:
        avail = {
            'codes' : [],
            'ids' : [],
        }
        for num, item in enumerate(separate):
            if len(avail['codes']) == 0:
                avail['codes'] = whs[item]
                avail['ids'].append(item)
            else:
                avail_all = list(set(avail['codes']) & set(whs[item]))
                print '%s : %s' % (item, avail_all)
                if len(avail_all) > 0:
                    avail['codes'] = avail_all
                    avail['ids'].append(item)
            if len(avail['codes']) > 0:
                del separate[num]
        submit.append(avail)
    return submit

返回结果:

[
    {
        'ids': ['ID4', 'ID3'], 
        'codes': ['code6']
    },
    {
        'ids': ['ID2'], 
        'codes': ['code2', 'code5', 'code3']
    },
    {
        'ids': ['ID1'],
         'codes': ['code1', 'code2', 'code3']
    }
]

除了 ID1 和 ID2 应该组合为

之外，它可以工作

{
    'ids' : ['ID1', 'ID2',],
    'codes' : ['code2', 'code3', ]
}

很好奇是否有一种我没有想到的更简单的方法，我想我可以设置更多的嵌套循环来逐个比较所有内容，尽管它看起来相当不Python

提前谢谢您

Answer 1

我通过构建所有潜在添加项的树来攻击它，然后在其中找到最便宜的选项。这是一个有效的示例(尽管丑陋且未经优化):

https://gist.github.com/1288835

树最终将有 p*w 个节点，其中 p 是产品数量，w(p) 是每个产品的平均仓库数量。