[Tutor] Dictionaries

[Rogério Brito]

On Jun 28 2002, Terje Johan Abrahamsen wrote:
> I have two dictionaries consisting of numbers. Eg (1:2,2:4,3:6) and 
> (1:5,2:6,3:9). Then I want to add the entries together in all possible 
> ways, to see if the numbers in dictionary 1 equals the numbers in 
> dictionary 2. (Eg, here entry 1 & 2 equals entry 2 in dictionary 2. Both 
> equals 6).

	Humm... This is getting interesting.

	By saying "in all possible ways", do you mean that you want to
	know if, for each key:value pair from the second dictionary,
	there is a subset of key:value pairs from the first dictionary
	such that the sum of values of the pairs from the subset
	equals the value of the key of the given pair from the second
	dictionary?

	In other words, do you want the following (in pseudocode):

	for (k, v) in dict_2.items():
	    for each subset of items from dict_1:
	        if v = sum_of_values(subset):
		   # print item (k, v) is "present" on dict_1
		else:
		   pass

	If this is what you want, then there are bad news for you, as
	this is a very hard (and classic) problem in computer science.
	This problem is called the "Subset Sum" and it is a
	NP-complete problem. This means that nobody knows an efficient
	algorithm to solve it besides "trying everything"
	(essentially).

	In fact, you are looking for many times the "Subset Sum"
	problem (one for each item from dict2).

	So, you will probably have to do an exhaustive search.

	If this is not what you meant, then please rephrase it and we
	can try to help you another way.

	BTW, I am a newbie in Python.


	[]s, Roger...

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Rogério Brito - linuxconsult@yahoo.com.br - http://www.ime.usp.br/~rbrito
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=