0

I'm trying to learn a bit about dynamic programming and had a peice of code that creates a table of data, but I'm having a hard time figuring out what certain parts do.

Here's the code:

from collections import defaultdict


data = [1, 2, 4]
sum = 10

# T[x, i] is True if 'x' can be solved
# by a linear combination of data[:i+1]
T = defaultdict(bool)           # all values are False by default
T[0, 0] = True                # base case

for i, x in enumerate(data):    # i is index, x is data[i]
    #print i, x
    for s in range(sum + 1): #set the range of one higher than sum to include sum itself
        #print s
        for c in range(s / x + 1):  
            if T[s - c * x, i]:
                T[s, i + 1] = True

I'm slowly starting to figure out how this code works but the second last line if T[s - c * x, i]: is a bit hard because I cannot replicate it fully in a terminal. When I type something simlair(using the values), it creates a matrix like [1,2] but how can that be true or false so it proceeds to the statement below?

If it helps, its part of some code that helps break down numbers. So I'm trying to figure out all the ways to break down 1,2,4 into 10. In this question, Can brute force algorithms scale?, I was suggested to create a dynamic table to reference.

Here's the end result(which I'm having trouble interpreting the results):

{(7, 3): True, (1, 3): True, (9, 1): True, (3, 0): False, (8, 0): False, (2, 1): True, (6, 2): True, (5, 1): True, (0, 3): True, (10, 3): True, (7, 2): True, (4, 0): False, (1, 2): True, (9, 0): False, (3, 3): True, (8, 1): True, (6, 3): True, (5, 0): False, (2, 2): True, (10, 0): False, (4, 1): True, (1, 1): True, (3, 2): True, (0, 0): True, (8, 2): True, (7, 1): True, (9, 3): True, (6, 0): False, (2, 3): True, (10, 1): True, (4, 2): True, (1, 0): False, (5, 3): True, (0, 1): True, (8, 3): True, (7, 0): False, (9, 2): True, (6, 1): True, (3, 1): True, (2, 0): False, (4, 3): True, (5, 2): True, (0, 2): True, (10, 2): True}

Any clarification or suggestions of what to read up on to help understand would be great!

Thanks!

Community
  • 1
  • 1
Lostsoul
  • 25,013
  • 48
  • 144
  • 239
  • `T[x,y]` means "get item (x,y) from the table". So `if T[1,2]` looks up (1,2) in the table, and uses the True or False from there. (As your comment says, "all values are False by default") – Thomas K Feb 09 '12 at 17:33

2 Answers2

1

Not sure I fully undestand the question.

If the tuple (x, y) exists in dictionary T, then T[x, y] will just return True or False according to what has been saved to it. If (x, y) does not already exist, because of T = defaultdict(bool), a non-existing key will cause bool() to be called, which returns False. You can replace the bool with some custom function to make this clearer

>>> from collections import defaultdict
>>> def on_missing():
...     print("missing key!")
...     return 'empty!'
... 
>>> T = defaultdict(on_missing)
>>> T[0, 0] = True     # Store 'True' for key (0, 0) in T
>>> T[0, 0]            # Retrieve the stored value
True
>>> T[1, 2]            # (1, 2) does not exist, so call on_missing()
missing key!
'empty!'       
>>> T[1, 2] = True     # Now store a value for (1, 2)
>>> T[1, 2]            # We can see 'True' is stored.
True

Since you are only assigning True, the condition if T[s - c * x, i]: is basically just checking whether (s-c*x, i) has been assigned manually or not. Normally we'll use a set() for that.

kennytm
  • 510,854
  • 105
  • 1,084
  • 1,005
  • This is where I'm a bit confused. If its not added to the dict, then nothing should be there so how are the results true? For example, if you print T at the start, its defaultdict(, {(0, 0): True}) I don't understand how that if statement can ever be true if there's nothing adding values to the T variable – Lostsoul Feb 09 '12 at 17:37
  • If I add an print T under the first for statement I see the table is being built, but I don't see anywhere in the code adding anything other than true values, so how are false or any values being added to the table? – Lostsoul Feb 09 '12 at 17:41
  • 1
    @Lostsoul: That's the magic of [`defaultdict`](http://docs.python.org/library/collections.html#collections.defaultdict). If you create `d = defaultdict(foo)`, and call `d[k]`, when `k not in d`, the function `foo()` will be called and that value is returned. You can check: http://ideone.com/DVFs3 – kennytm Feb 09 '12 at 17:47
  • omg thats amazing! I didn't know that..So the T = defaultdict(bool) is what made everything not specifically in T to return as false. I get it now. Okay LAST question(and then I'll stop bugging you, promise!) At the end of this script if I do 'print T', it has a table of results and there are some false results in there. How do they get saved in there if they aren't specifically being added(we seem to only be saving true variables)? I understand making a reference and its not there, but 'print t' should display what's saved and not something like '(3, 0): False'? how does this happen? – Lostsoul Feb 09 '12 at 17:57
  • even in your example above, your explicitly saying T[1, 2] = True, but if you didn't and did a print T, how would it have anything with a value of false? – Lostsoul Feb 09 '12 at 17:59
  • @Lostsoul: If the key is missing, the `bool()` will be called and the result is inserted back to the dictionary. "[If `default_factory` is not `None`, it is called without arguments to provide a default value for the given *key*, **this value is inserted in the dictionary for the *key*, and returned**.](http://docs.python.org/library/collections.html#collections.defaultdict.__missing__)" – kennytm Feb 09 '12 at 18:00
  • thanks so much its clear now. I'll read up on defaultdict. Thanks for taking the time to explain and teach me. Thanks so much! – Lostsoul Feb 09 '12 at 18:04
0

Not sure I understand your question, but the syntax seems to be pretty straightforward here. T is defaultdict, so T[s - c * x, i] is accessing the value by key, where key is (s - c * x, i). All values in T are False by default, and the code updates some of them to True in last line.

Roman Bataev
  • 9,287
  • 2
  • 21
  • 15