时间戳

首页 > 解决方案 > 使用python从字典中提取客户端服务器的顺序

python - 使用python从字典中提取客户端服务器的顺序

问题描述

我有一个像下面这样的字典，例如，第一个项目意味着 5 是 2 的客户。在最后一个项目中，如您所见，2 是 4 的客户，4 也是项目 3 的客户。

customer_provider_dic= {'2':['5'],'1':['2'],'3':['4'],'4':['2']}

我正在尝试提取这些项目的所有客户链。输出将是这样的：

[2,5]
[1,2,5]
[3,4,2,5]
[4,2,5]

我真的很困惑如何提取这些链。对流程图或我应该遵循的步骤的任何建议。

标签： pythonlistdictionarysequence

解决方案

首先，如果所有列表都只包含一个项目，这是一个可行的解决方案。

def simple_chain(graph, key):
    chain = [key]
    while True:
        lst = graph.get(key)
        if lst is None:
            # There's nothing left to add to the chain
            break
        key = lst[0]
        if key in chain:
            # We've found a loop
            break
        chain.append(key)
    return chain

customer_provider = {
    '2': ['5'], '1': ['2'], '3': ['4'], '4': ['2'],
}

data = customer_provider
for k in data:
    print(simple_chain(data, k))

输出

['2', '5']
['1', '2', '5']
['3', '4', '2', '5']
['4', '2', '5']

一般的解决方案有点困难。我们可以使用递归生成器创建所有链。下面的代码有效，但效率不高，因为它多次生成相同的子链。

基本策略与之前的版本类似，但我们需要遍历每个列表中的所有键，并为每个键创建一个新链。

要完全理解这段代码的工作原理，您需要熟悉递归和 Python生成器。您可能还会发现此页面很有帮助：了解 Python 中的生成器；网上也有各种 Python 生成器教程。

def make_chains(graph, key, chain):
    ''' Generate all chains in graph that start at key.
        Stop a chain when graph[key] doesn't exist, or if
        a loop is encountered.
    '''
    lst = graph.get(key)
    if lst is None:
        yield chain
        return
    for k in lst:
        if k in chain:
            # End this chain here because there's a loop
            yield chain
        else:
            # Add k to the end of this chain and
            # recurse to continue the chain
            yield from make_chains(graph, k, chain + [k])

customer_provider = {
    '2': ['5'], '1': ['2'], '3': ['4'], '4': ['2'],
}

pm_data = {
    '2': ['5'], '1': ['2'], '3': ['4', '6'], 
    '4': ['2'], '6': ['1', '5'],
}

#data = customer_provider
data = pm_data

for k in data:
    for chain in make_chains(data, k, [k]):
        print(chain)

如果我们使用它运行该代码，data = customer_provider则会产生与先前版本相同的输出。这是运行时的输出data = pm_data。

['2', '5']
['1', '2', '5']
['3', '4', '2', '5']
['3', '6', '1', '2', '5']
['3', '6', '5']
['4', '2', '5']
['6', '1', '2', '5']
['6', '5']

yield from语法是 Python 3 的一个特性。要在 Python 2 上运行此代码，请更改

yield from make_chains(graph, k, chain + [k])

至

for ch in make_chains(graph, k, chain + [k]):
    yield ch

在 Python 3.6 之前，dict不保留键的插入顺序，因此可以按任意顺序for k in data遍历键。data但是，输出列表仍然是正确的。您可能希望将该循环替换为

for k in sorted(data):

让链条井然有序。

推荐阅读