Извлечение порядка клиентского сервера из словаря с использованием Python

Question

У меня есть словарь, подобный приведенному ниже, который, например, для первого элемента означает 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]

Я действительно запутался, как я могу извлечь эти цепи. Любое предложение для блок-схемы или шагов, которые я должен следовать.

Answer 1

Во-первых, вот решение, которое работает, если все списки содержат ровно один элемент.

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']

---

Общее решение немного сложнее. Мы можем создать все цепочки, используя рекурсивный генератор. Приведенный ниже код работает, но он не очень эффективен, поскольку он создает одни и те же подцепи несколько раз.

Базовая стратегия аналогична предыдущей версии, но нам нужно перебрать все ключи в каждом списке и создать новую цепочку для каждого из них.

Чтобы полностью понять, как работает этот код, вы должны быть знакомы с recursion и с генераторами 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):

чтобы привести цепи в порядок.