[Tutor] addition

[Emil Styrke]

"Terje Johan Abrahamsen" <terjeja@hotmail.com> writes:

> Hello,
>=20
>     I have to make a program that compares policies for an accounting
> department. It uses two different systems, AS/400 and Win Excel. I
> have built all the surounding code moving numbers back and forth,
> formatting and so forth, but the main calculations are missing. Here
> is the problem:
>=20
> In Excel up to 7 accounts can have the same policynumber, while up to
> 3 policies in the AS/400 system can have the same policynumber. Any
> number of policies in either system can match any number of policies
> in the other system. So, therefore for example 5 Excel amounts can add
> up to the approximate amount (+-$5) of 2 AS/400 accounts. If this is
> the case, these amounts should be marked. If I haven't forgotten all
> my statistics skills, that should equal up to (7!=3D5040 * 3!=3D6)=3D30240
> calculations. How can I do this? There is no way I can use my normal
> way of doing this (with less numbers) by writing in the possibilities,
> as in if a+b=3Dc:print yes, elif a+c =3D d: print yes and so forth until I
> have used all the possibilities. I need the computer to do this part
> this time. (I am a beginner, so please keep it simple.)
>

I'm not sure I understand the problem.  You want to find if a subset
of up to seven numbers adds up to approximately the same as a subset
of up to three other numbers?  In that case, the code below might do
it, although i'm sure there are better and faster ways to do it.  The
trick is to first calculate lists of all possible sums of each of the
sets and then compare them with each other.

I've intentionally left out some idioms in order to make the code
easier to understand.  Feel free to ask questions if something is
unclear!

        /Emil

#  This function takes a set of items (numbers in your case) and returns
#  a list of all possible subsets of it. (including the empty set)
#  It does this by calling itself recursively.  This concept is not the
#  easiest one to grasp for a beginner, but i couldn't find a better way.
#  If you like to, just consider it a "black box" and ignore its inner
#  workings. :)
#
#  (If you try this one out, you'll see that there are 2^n combinations
#  for a set with n elements, and not n!. (I'm too tired right now
#  to try to find out why...)
def powerset(set, res=3D[[]]):
  if len(set) =3D=3D 0:
    return res                  # If the set is empty, return our saved res=
ult
  first_element =3D set[0]        # Get the first element of the set
  other_elements =3D set[1:]      # And the rest
  new_elements =3D []             # Now we calculate a list of new elements
                                # to add to our result.  To do that we
                                # iterate through the subsets we already
                                # have and append the current element to
                                # them.
  for i in res:
    new =3D i[:]                  # We have to copy the list first, or else
                                # the original will be changed too, and
                                # we don't want that.
    new.append(first_element)
    new_elements.append(new)
  return powerset(other_elements, res + new_elements)  # Finally, we call
                                # powerset again, but with the first
                                # element of "set" removed, and our new
                                # elements added to the result variable.

#  This function takes a set of numbers and returns a list of sums of all
#  possible subsets.
def makesums(set):
  combinations =3D powerset(set)  # Get a list of combinations by calling
                                # powerset.

  sums =3D []                     # initialize the list of sums

  for i in combinations:        # Go through all the combinations
    sum =3D 0                     # Initialize the current sum to 0
    if len(i) =3D=3D 0:		# If there are no numbers in this set,
        continue		# skip to the next.
    for j in i:                 # Go through all the numbers in this subset=
..
      sum =3D sum + j             # ..and add them to "sum"
    sums.append(sum)            # Finally, we add each sum to the list of s=
ums
  return sums                   # ..and return it

# This function takes two sets (lists) of numbers and prints out "yes"
# if there is a subset of elements in set1 which add up to a subset of
# elements in set2, +-5.
def search(set1, set2):
  match =3D 0
  sums1 =3D makesums(set1)        # Get the first list of sums
  sums2 =3D makesums(set2)        # Get the second list of sums
  for i in sums1:               # For each of the first list of sums
    for j in sums2:             # Go through the second list of sums
      if i - 5 < j and i + 5 > j:  # And check if they are within +-5 of
        match =3D 1               # each other.
  if match =3D=3D 0:
    print "no"
  else:
    print "yes"
=20=20
> Thanks,
> Terje
>=20
>=20
>=20
> _________________________________________________________________
> Join the world=92s largest e-mail service with MSN
> Hotmail. http://www.hotmail.com
>=20
>=20
>=20
> _______________________________________________
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor