0

I've been trying to understand recursion/recursivity in programming languages and I've chosen to work with python, since it's the language I understand the most. I've tried resolving the following problem -

Given three different lists of elements, find all the possible patterns that a certain person has followed during his shopping day.

Lists

purchases = [[money_spent, time0], [money_spent, time1], [money_spent, time3]]

time_between_shops = [[time_to_self, time_to_shop2, time_to_shop3, time_to_shop4],
                     [time_to_shop1, time_to_self, time_to_shop3, time_to_shop4],
                     [time_to_shop1, time_to_shop2, time_to_self, time_to_shop4],
                     [time_to_shop1, time_to_shop2, time_to_shop3, time_to_self]]

list_of_products = [["shop1", {"product1": price_of_product1, "product2": price_of_product2}],
                    ["shop2", {"product3": price_of_product3, "product4": price_of_product4, "product5": price_of_product5}],
                    ["shop3", {"product6": price_of_product6}],
                    ["shop4", {"product7": price_of_product7}]]

In those lists purchases are ordered by their time (earliest to latest purchase) and shops have the same indexes in the list_of_products as in time_between_shops. Time between shops can be the same, but the time it takes to go from shop A to shop B can be different from the time it takes to go from shop B to shop A. The given time is in minutes where 0 is 0:00 and 1439 is 23:59.

Given that information, I know how to approach this problem the regular way, however I need to use recursive methods to obtain all the possibilities. I've read up on recursive methods, so I know what they represent, and when I see one I can understand what it does and how it works, but when it comes to creating recursive methods on my own, I get lost since I always go back to regular methods.

So how should I approach this problem in order to resolve it using recursion instead of the regular methods?

Iocust
  • 105
  • 1
  • 14
  • What are the "*regular methods*" you are talking about? – miradulo Apr 02 '15 at 14:00
  • By "regular methods" I mean there might be ways of resolving this by using a non-recursive algorithm, however I haven't thought in that direction because that's not how I'm supposed to solve the problem. There might as well be none, I haven't tried to go in that direction enough for me to say if any of them would work. – Iocust Apr 02 '15 at 14:22
  • In its current state your problem does not seem exactly *solvable*. Do you have values for the travel times? Expected input and output? Or are we trying to calculate the number of possible iterations? – miradulo Apr 02 '15 at 14:38
  • @Donkey Kong I have fixed values of the time traveled between shops. All the values exist, I just tried to generalize the problem. Here is what I should give to the program `time_between_shops = [[0,5],[7,0]] purchases = [[28.79,[15,57]],[13,[16,4]] list_of_products = [["shop1", {'Bananas':5, 'Candy':3, 'Books':7.95}], ["shop2", {'Keyboard':20, 'Gloves':5, 'Ring':3.79, 'Horse Toy':8.79, '5kg of rice':10.95}]]` and the expected output is all the possibilities for the person's shopping route. Here, the shops at shop1 for 28,79 dollars and then goes to shop2 and spends 13 dollars. – Iocust Apr 02 '15 at 14:55
  • I think that this http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum subset sum algorithm can help me out in finding all possible combinations of articles for the purchase in a single shop. What remains after that is finding all route possibilities. – Iocust Apr 02 '15 at 15:17

0 Answers0