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?

fceruti · Accepted Answer · 2015-04-03 05:29:55Z

2

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

answered Apr 3, 2015 at 5:29

fceruti

2,4551 gold badge21 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Definitely Blitzkrank Over a year ago

Thank you! I understand the basics of tree structures, however I have never worked with them. Is there a way to use the solution you provided in order to obtain a reusable representation of the possible routes that I can use? For example a dictionary that would contain as keys the starting points, and as values to the keys all the routes that start from that point? I am asking because this is part of a slightly bigger project that needs to use those values. Thank you very much!

fceruti Over a year ago

ofcourse you can, you just need to take that output, and transform it into what you want. I'll leave that challenge for you thou :)

Definitely Blitzkrank Over a year ago

I'm on it then! By the way, is there a simple way of setting it so that there is no repetition in the algorithm? For example, if I want to exclude routes of the type shop1 -> shop2 -> shop1. Or perhaps is it inefficient to do it like that?

fceruti Over a year ago

you certainly can, but you need to store things differently so you have access to the "history" of the node.

Collectives™ on Stack Overflow

Finding all combinations in a list with a constraint in python

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related