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

商店只能访问一次。我们可以看到，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个possiblities的输出 - >开始从SHOP2 = [2,0,1]和 - >从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 :) 

那么，这里是脚本。如果你有任何疑问只是问:)

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