Нахождение всех комбинаций в списке с ограничением в питоне

Обновить

December 2018

Просмотры

123 раз

3

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

Например

list_of_shops = [shop1, shop2, shop3, shop4] 
# Index for this list and the one below are the same

list_of_time_it_takes = [[0, 2, 1, 4], [2, 0, 1, 4], [2, 1, 0, 4], [1, 2, 3, 0]]
# the 0 indicates the index of the shop. It takes 0 minutes to reach the shop from itself.

list_of_time_intervals = [0, 2, 2]

Магазины можно посетить только один раз. Мы можем видеть, что 3 магазина были посещены в 2-минутных интервалах и что возможные маршруты:

shop4> Shop2> shop1

shop3> shop1> Shop2

Так что я пытаюсь решить эту проблему выше желаемых результатов, используя следующий код:

shops = [[0, 2, 1, 4, 9], [2, 0, 1, 4, 9], [2, 1, 0, 4, 9], [1, 2, 3, 0, 11], [3, 6, 16, 4, 0]]
times = [0, 2, 2, 4, 11]
list_of_shops = ['shop0', 'shop1', 'shop2', 'shop3', 'shop4']
index_dict = {}



def function(shops_input, times_input, i, index_list):

    #print("given i = ", i)
    #print("given shops = ", shops_input)
    #print("given times = ", times_input)

    shops_copy, times_copy = shops_input[:], times_input[:]
    pop = times_copy.pop(0)
    #print("obtained pop = ", pop)
    if shops[i] in shops_copy:

        index_list.append(shops.index(shops[i]))
        shops_copy.pop(shops_copy.index(shops[i]))
        if len(index_list) == len(times):
            index_dict[list_of_shops[index_list[0]]] = index_list
            print(index_list)
            print(index_dict)
        if len(times_copy):
            try:
                function(shops_copy, times_copy, shops[i].index(times_copy[0]), index_list)
            except ValueError:
                return


def main_function(shops, times):
    for i in range(len(shops)):
        function(shops, times, i, [])
        print("---------end funct---------")


main_function(shops, times)

И это работает в некоторых случаях, но, безусловно, не во всех случаях. Он должен дать мне все возможные маршруты, основанные на заданные интервалы времени, однако, это не похоже на работу в большинстве случаев.

Например, если я изменю магазины и раз:

shops = [[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]]
times = [0, 1, 1]

это дает выход 2 идей! -> начиная с Shop2 = [2,0,1] и -> начиная с shop3 = [3,0,1]. Есть ли способ, чтобы сделать мой алгоритм работы?

1 ответы

2

Я написал небольшой скрипт, который решает проблему. Во-первых, давайте посмотрим на выходе. Это словарь, который представляет собой дерево. Корневой элемент должен держать все вместе. Все остальные дети (или листья), возможны визиты при условии, что вы на этом узле (или магазина).

{'children': [{'children': [{'children': [{'children': [{'children': [{'children': [],
                                                                       'shop': 4}],
                                                         'shop': 3}],
                                           'shop': 0}],
                             'shop': 1}],
               'shop': 0},
              {'children': [{'children': [{'children': [{'children': [{'children': [],
                                                                       'shop': 4}],
                                                         'shop': 3}],
                                           'shop': 1}],
                             'shop': 0}],
               'shop': 1},
              {'children': [{'children': [{'children': [{'children': [{'children': [],
                                                                       'shop': 4}],
                                                         'shop': 3}],
                                           'shop': 1}],
                             'shop': 0}],
               'shop': 2},
              {'children': [{'children': [{'children': [{'children': [{'children': [],
                                                                       'shop': 4}],
                                                         'shop': 3}],
                                           'shop': 0}],
                             'shop': 1}],
               'shop': 3},
              {'children': [], 'shop': 4}],
 'shop': 'root'}
Drink beer :)

Ну, а вот сценарий. Если у вас есть какие-либо сомнения, просто спросить :)

shops = [[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]]
times = [0, 1, 1]

"""
Data structure
{
    shop: 'root',
    children: [
        {
            shop: 1,  # index of the shop
            children: [  # shops where you can go from here
                {
                    shop: 2,
                    children: [...]
                }, 
                ...
            ]
        },
        ...
    ]
}

"""

def get_shop(index):
    return shops[index]


def get_next_shop_indexes(shop, time_interval):
    next_shops = []
    for index, shop_time_interval in enumerate(shop):
        if shop_time_interval == time_interval:
            next_shops.append(index)
    return next_shops


def build_route_branch(branch, shop_index, time_intervals):
    shop = get_shop(shop_index)
    next_shop_indexes = get_next_shop_indexes(shop, time_intervals[0])
    for next_shop_index in next_shop_indexes:
        child_branch = {
            'shop': next_shop_index,
            'children': []
        }
        branch['children'].append(child_branch)
        if len(time_intervals) > 1:
            child_branch = build_route_branch(
                child_branch, 
                next_shop_index, 
                time_intervals[1:]
            )

tree = {
    'shop': 'root',
    'children': []
}
for index, shop in enumerate(shops):
    branch = build_route_branch(tree, index, times)

import pprint
pprint.pprint(tree)

print 'Drink beer :)'