[Tutor] Dictionaries [lists]

[Danny Yoo]

> I think I am even newer in Python than you, so I can't really for sure
> tell if the pseudocode actually is what I want. But, I can explain a
> little more detailed:
>
> dict1 = (1:2,2:4)
> dict2 = (1:5,2:6)
>
> Then dict1 can have the following sums:
>
> 2,4 and 6
>
> While dict2 can have the following sums:
> 5,6 and 11


Ah!  If I understand your problem correctly, I think that the dictionary
is not an appropriate structure for what you're doing.  It might be better
just to keep the summing numbers in a list:

###
first_numbers = [2, 4]
second_numbers = [5, 6]
###

If your keys are always going to be sequential numbers starting from 0 or
1, then your problem probably should use lists, not dictionaries.




> What I have started on doing, is the following: Calculate all the
> possibilities for dict1. That gives me 7 variables if it is 3 entries.
> Then I can make some function that calculates one by one of the sums for
> dict2 and then compare it to the 7 sums. It is this second part that is
> stopping me now. I do not want to write out everything as with dict1.
> (As pasted in below, for specially interested..)

Sounds good; if we have a list of numbers, we can calculate all the
possible sums of those numbers.  Let's call this function 'allSums()'.
We can imagine that allSums([2, 4]) returns the list: [2, 4, 6], and we
can also imagine that allSums([5, 6]) returns the list [5, 6, 11].

There is a nice solution to this problem that uses a technique called
"dynamic programming" --- we try to find the solution for the smallest
version of the problem, and then work our way up, improving things until
we get the correct answer.



For example, if we wanted to find allSums([3, 4, 5, 6]), a "dynamic
programming" approach would ask the following questions:

    Question 1: What's allSums([3])?
    Question 2: What's allSums([3, 4])?
    Question 3: What's allSums([3, 4, 5])?
    Question 4: What's allSums([3, 4, 5, 6])?

(We're interested in the answer to Question 4.)

The trick that makes dynamic programming neat is that the answer to
Question 1 actually is useful when we do Question 2.  Likewise, the answer
to Question 2 can make Question 3 really easy to answer.  For those who
have seen recursion before, this will seem very familiar, although the
flow of the questions goes in reverse!

I'll post one possible way of doing this at the bottom of this message.
Skip if you don't want to be spoiled.  *grin*

*** Spoiler space ahead ***
















*** Spoiler space ***

###
def allSums(numbers):
    """Returns all possible sums of any nonempty subset of elements
in 'numbers'."""
    possible_sums = [numbers[0]]
    for n in numbers[1:]:
        possible_sums.extend([n + sum for sum in possible_sums])
        possible_sums.append(n)
    return possible_sums
###


How would this calculate allSums([3, 4, 5])?

It first tries to figure out allSums([3]), and this one is really easy.

    allSums([3]) == [3]

There's only one sum involved here, so we can just say that if we're
trying to find all possible sums from [3], that just comes out to [3].


The second answer ia also pretty easy: if we know allSums([3]), then we
can either add 4, or not add 4, or start off a new sum by using 4:

    allSums([3, 4]) ==
        ... Just the values of allSums([3])

        ... plus all the results of:  [(4 + sum)
                                       for sum in allSums([3])]
        ... plus just plain "4".


The third answer is also pretty easy: if we know allSums([3, 4]), then we
can either add 5, or not add 5, or start off a new sum by using 5:

    allSums([3, 4, 5]) ==
        ... Just the values of allSums([3, 4])

        ... plus all the results of:  [(4 + sum)
                                       for sum in allSums([3, 4])]
        ... plus just plain "5".



Hope this helps!