在python中查找具有约束的列表中的所有组合

Question

我最近一直在努力学习递归算法，结果遇到了死胡同。给定一定数量的列表，每个列表代表从一个商店到所有其他商店所需的时间，以及一个包含时间间隔序列的列表，有没有一种方法可以使用递归性来查找商店之间所有可能的路线？在

例如

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家商店，可能的路线是：

shop4 > shop2 > shop1

shop3 > shop1 > shop2

因此，我尝试使用以下代码来解决上述问题：

^{pr2}$

它在某些情况下是有效的，但绝对不是所有的情况。它应该根据给定的时间间隔给我所有可能的路线，但是，在很多情况下它似乎不起作用。在

例如，如果我将商店和时间更改为：

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

它提供2个可能的输出->；starting from shop2=[2,0,1]和->；starting from shop3=[3,0,1]。有没有办法让我的算法有效？在

Answer 1

我写了一个小脚本来解决你的问题。首先让我们看看输出。这是一本代表树的字典。根元素是把所有的东西放在一起。如果您在该节点（或商店），则所有其他子节点（或树叶）都是可能的访问。在

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

好吧，这是剧本。如果您有任何疑问，请询问：）

^{pr2}$