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