[C++-sig] Need to understand the following Python Program- He lp me..

[Max Khesin]

Wrong forum - this one is dedicated to Python/C++ binding. Please try
comp.lang.python on Usenet, or better yet google "karp algorithm" - I am
sure you will find many implementations.

max

-----Original Message-----
From: jaeho kim [mailto:jaehokim1 at yahoo.com]
Sent: Friday, April 29, 2005 11:19 AM
To: c++-sig at python.org
Subject: [C++-sig] Need to understand the following Python Program- Help
me..

Hi,,,

I am very interested about the following Python program, but I am
very beginner on Python.. I do not understand this algorithm,,

I would appreciated if you give me this algorithm to some other
popular programming language.


filename="Karp.py"




from __future__ import nested_scopes

import bisect

class _Num:
    def __init__(self, value, index):
        self.value = value
        self.i = index

    def __lt__(self, other):
        return self.value < other.value

# This implements the Karmarkar-Karp heuristic for partitioning a set
# in two, i.e. into two disjoint subsets s.t. their sums are
# approximately equal.  It produces only one result, in O(N*log N)
# time.  A remarkable property is that it loves large sets:  in
# general, the more numbers you feed it, the better it does.

class Partition:
    def __init__(self, nums):
        self.nums = nums
        sorted = [_Num(nums[i], i) for i in range(len(nums))]
        sorted.sort()
        self.sorted = sorted

    def run(self):
        sorted = self.sorted[:]
        N = len(sorted)
        connections = [[] for i in range(N)]

        while len(sorted) > 1:
            bigger  = sorted.pop()
            smaller = sorted.pop()

            # Force these into different sets, by "drawing a
            # line" connecting them.
            i, j = bigger.i, smaller.i
            connections[i].append(j)
            connections[j].append(i)

            diff = bigger.value - smaller.value
            assert diff >= 0
            bisect.insort(sorted, _Num(diff, i))

        # Now sorted contains only 1 element x, and x.value is
        # the difference between the subsets' sums.

        # Theorem:  The connections matrix represents a spanning tree
        # on the set of index nodes, and any tree can be 2-colored.
        # 2-color this one (with "colors" 0 and 1).

        index2color = [None] * N

        def color(i, c):
            if index2color[i] is not None:
                assert index2color[i] == c
                return
            index2color[i] = c
            for j in connections[i]:
                color(j, 1-c)

        color(0, 0)

        # Partition the indices by their colors.
        subsets = [[], []]
        for i in range(N):
            subsets[index2color[i]].append(i)

        return subsets

N = 50
import math
x = [math.sqrt(i) for i in range(1, N+1)]
p = Partition(x)
s, t = p.run()
sum1 = 0L
sum2 = 0L
for i in s:
    sum1 += x[i]
for i in t:
    sum2 += x[i]
print "Set 1 sum", repr(sum1)
print "Set 2 sum", repr(sum2)
print "difference", repr(abs(sum1 - sum2))


Thanks for you help...

Larry Jaeho Kim


Larry Jaeho Kim

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
_______________________________________________
C++-sig mailing list
C++-sig at python.org
http://mail.python.org/mailman/listinfo/c++-sig
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the system manager. This message contains confidential information and is intended only for the individual named. If you are not the named addressee you should not disseminate, distribute or copy this e-mail.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/cplusplus-sig/attachments/20050429/21dd6ac9/attachment.htm>