在Python中查找具有约束条件的列表中的所有组合

Question

在Python中查找具有约束条件的列表中的所有组合

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]

商店只能被访问一次。我们可以看到在2分钟间隔内已经访问了3个商店，可能的路线有：

商店4 > 商店2 > 商店1

商店3 > 商店1 > 商店2

所以我正在尝试使用以下代码解决上述问题并得到期望的输出：

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,0,1] 和 [3,0,1] 开始执行。是否有办法让我的算法正常工作？

- Definitely Blitzkrank

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fceruti · Accepted Answer

我写了一个小脚本来解决你的问题。首先让我们看一下输出。它是一个代表树形结构的字典。根元素用于将所有内容组合在一起。其他所有子元素（或叶子）都是可能的访问，前提是你在该节点（或商店）。

{'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 :)'