Finding all combinations in a list with a constraint in python

Question

I've been trying to learn recursive algorithms lately, and I've run into a dead end. Given a certain number of lists, each of which represents the time it takes to go from one shop to all others, and a list containing a sequence of time intervals, is there a way to find all possible routes between shops using recursivity?

For example

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]

Shops can only be visited once. We can see that 3 shops have been visited at 2 minute intervals and that the possible routes are:

shop4 > shop2 > shop1

shop3 > shop1 > shop2

So I'm trying to resolve the problem above with the desired output using the following code:

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)

And it works in some cases, but definitely not in all cases. It's supposed to give me all the possible routes based on the given time intervals, however, it doesn't seem to work in a lot of cases.

For example if I change shops and times to:

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

it gives an output of 2 possiblities -> starting from shop2 = [2,0,1] and -> starting from shop3 = [3,0,1]. Is there any way to make my algorithm work?

Answer 1

I wrote a little script that solves your problem. First lets look at the output. It's a dictionary that represents a tree. The root element is to hold everything together. All the other children (or leaves), are possible visits given that you are on that node (or shop).

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

Well, and here is the script. If you have any doubts just ask :)

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