473,554 Members | 2,480 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Need some help to understand Python program..


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) )]
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

diff = bigger.value - smaller.value
assert diff >= 0
bisect.insort(s orted, _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
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):

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...

Jul 19 '05 #1
0 1129

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

by: Jeff Wagner | last post by:
I am in the process of learning Python (obsessively so). I've been through a few tutorials and read a Python book that was lent to me. I am now trying to put what I've learned to use by rewriting that Numerology program I wrote years ago in VB. There are times I am totally stuck (for instance, I just had an idea to put the numerical values of...
by: Alex Pavluck | last post by:
Hello. I am trying to teach myself PYTHON because I am interested in programming. I use SAS all day and I really like the way you can highlight code and submit just that section or submit the entire program without having to save it. Can you do this in PYTHON? Also, does PYTHON (Windows) log errors? It would be helpful when I am writting...
by: Joh | last post by:
hello, i'm trying to understand how i could build following consecutive sets from a root one using generator : l = would like to produce : , , , ,
by: Heather Stovold | last post by:
Wow - deciding to program in python sure requires a lot of decisions! So far: I've decided on python for the programming language. I've decided on wxpython for the GUI.... I've decided on DrPython for the Editor.... I still need to decide on a database........ I've really only used Access, and my SQL skills aren't that great. It...
by: Nathan Pinno | last post by:
Hi all, I need help figuring out how to fix my code. I'm using Python 2.2.3, and it keeps telling me invalid syntax in the if name == "Nathan" line. Here is the code if you need it. #This program asks for a password, then asks for the user's name after the correct password has been supplied. The computers response will vary, # depending...
by: Jon Monteleone | last post by:
Greetings, I posted a few days back and didnt get much of a response, so I figured I would post again with more detail. I am running gnome under fedora core 4. I want a kid to be able to drop a quarter into a coin slot and get 15 minutes of time on an account that has "restricted" Internet access via the firefox web browser. We are...
by: wipit | last post by:
I need to process a HTML form in python. I'm using urllib2 and HTMLParser to handle the html. There are several steps I need to take to get to the specific page on the relevant site the first of which is to log in with a username/password. The html code that processes the login consists of 2 edit boxes (for User ID and Password) and a Submit...
by: LaundroMat | last post by:
Hi, I've found this script over at effbot (http://effbot.org/librarybook/os-path.htm), and I can't get my head around its inner workings. Here's the script: import os class DirectoryWalker: # a forward iterator that traverses a directory tree
by: adamurbas | last post by:
ya so im pretty much a newb to this whole python thing... its pretty cool but i just started today and im already having trouble. i started to use a tutorial that i found somewhere and i followed the instructions and couldnt get the correct results. heres the code stuff... temperature=input("what is the temperature of the spam?") if...
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.