Problem:list of elements, one is unique, others always in pairs, find unique

 

	def unique(arr):
	""" find unique element in array
	1. only one is unique
	2. all the others are in pairs
	>>> unique([1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1])
	6
	A XOR A = 0
	0 XOR A = A
	"""
	x = 0
	for i in arr:
	x ^= i
	return x

view raw unique hosted with ❤ by GitHub

 Handy itertools:

• powerset

  	import itertols as it
  	def powerset(iterable):
  	"""
  	powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
  	"""
  	s = list(iterable)
  	return it.chain.from_iterable(it.combinations(s, r) for r in range(len(s)+1))

  view raw powerset hosted with ❤ by GitHub
• all sublist from list

  	def sublists(iterable):
  	""" generate all of the sublist from *iterable*.
  	>>> [s for s in sublists('hi')]
  	[('h',), ('i',), ('h', 'i')]
  	>>> list(sublists([0, 1, 2]))
  	[(0,), (1,), (2,), (0, 1), (1, 2), (0, 1, 2)]
  	"""
  	# The length-1 sublist
  	seq = []
  	for item in iter(iterable):
  	seq.append(item)
  	yield (item,)
  	seq = tuple(seq)
  	item_count = len(seq)
  	# And the rest
  	for n in range(2, item_count + 1):
  	for i in range(item_count - n + 1):
  	yield seq[i : i + n]

  view raw sublists hosted with ❤ by GitHub

naive graph coloring

  Coloring nodes of a graph, simple and naive approach:

	#!/usr/bin/env python
	import random
	import sys
	class node( object ):
	""" a vertex
	"""
	def __init__( self, key ):
	""" c'tor """
	self.key = key
	self.c = None
	self.outEdges = []
	self.inEdges = []
	def connect( self, other ):
	""" connect this verted to the other one """
	if self not in other.inEdges and other not in self.outEdges:
	other.inEdges.append( self )
	self.outEdges.append( other )
	class graph( object ):
	""" simple graph """
	nodes = []
	def __init__( self ):
	""" c'tor """
	self.nodes = []
	self.chroma = 1
	self.palette = []
	def __contains__( self, node ):
	""" in operator """
	return node in self.nodes
	def add( self, n ):
	""" add vertex """
	if n not in self.nodes:
	self.nodes.append( n )
	def colors( self ):
	""" create random palette """
	while len(self.palette) < self.chroma:
	newcol = "#%s" % hex( random.randint(0, 256*256*256 ) )[2:].zfill(6)
	if newcol not in self.palette:
	self.palette.append( newcol )
	def dot( self, fname ):
	""" create dot file """
	self.colors()
	if not fname.endswith(".dot"):
	fname = "%s.dot" % fname
	fname = open( fname, "w+" )
	fname.write( "digraph G {\n")
	for node in self.nodes:
	fname.write( "%s [color=\"%s\",bgcolor=\"%s\",label=\"%s\",shape=\"circle\",style=\"filled\"];\n" % ( node.key,
	self.palette[node.c-1],
	self.palette[node.c-1],
	node.key ) )
	for node in self.nodes:
	for c in node.outEdges:
	fname.write( "%s -> %s;\n" % ( node.key, c.key ) )
	fname.write( "}\n" )
	fname.close()
	def color( gr ):
	""" colorize graph """
	for n in gr.nodes:
	n.c = None
	def colorize( n, col ):
	""" can use color c for vertex n? """
	for item in n.inEdges + n.outEdges:
	if item.c == col:
	return False
	return col
	# # sort by number of in and out edges
	nodes = sorted( [ (len(n.outEdges + n.inEdges), n) for n in gr.nodes ], reverse = True )
	colors = [ 1 ]
	for i, n in nodes:
	if not n.c:
	while not n.c:
	for c in colors:
	can = colorize( n, c )
	if can:
	n.c = can
	break
	if not n.c:
	colors.append( colors[-1] +1 )
	n.c = colors[-1]
	## set chromatic number
	gr.chroma = len(colors)
	return colors
	## execution
	if __name__ == "__main__":
	if len(sys.argv) != 4:
	print "usage: color.py nbNodes nbEdges dotFile"
	sys.exit(0)
	nodes, edges, fname = int(sys.argv[1]), int(sys.argv[2]), sys.argv[3]
	gr = graph()
	nodes = [ node(i) for i in range(nodes) ]
	for i in range(edges):
	inode = random.choice( nodes )
	jnode = random.choice( nodes )
	inode.connect( jnode )
	for node in nodes:
	gr.add(node)
	c = color(gr)
	gr.dot( fname )

view raw color.py hosted with ❤ by GitHub

Usage is very simple:

python color.py  nbNodes nbEdges dotFileName

and then use dot, neato or twopi for rendering.

Example gallery is here.

don't pay taxes for CO2 emission, just plant more red black trees

Just for fun and making plots like that [small rbtrees gallery].

And here goes the humble code...

	class Node( object ):
	"""
	.. class:: Node
	rbTree Node
	"""
	def __init__( self, key ):
	""" c'tor """
	self.left = None
	self.right = None
	self.red = False
	self.key = key
	self._parent = None
	@property
	def parent(self):
	return self._parent
	@parent.setter
	def parent( self, parent ):
	self._parent = parent
	def grandpa( self ):
	""" grandparent """
	if self.parent:
	return self.parent.parent
	def uncle( self ):
	""" uncle """
	grandpa = self.grandpa()
	if not grandpa:
	return None
	if self.parent == grandpa.left:
	return grandpa.right
	return grandpa.left
	class rbTree( object ):
	"""
	.. class:: rbTree
	as seen in T. Cormen, C. Leiseron, R. Rivest, C. Stein
	"""
	def __init__( self ):
	""" c'tor """
	# # dummy node
	self._null = Node(None)
	self._null.left = self._null
	self._null.right = self._null
	self._null.parent = self._null
	# # initial tree root
	self.root = self._null
	def insert( self, key ):
	""" insert key :key: into the tree """
	y = self._null
	x = self.root
	while x != self._null:
	y = x
	if key <= x.key:
	x = x.left
	else:
	x = x.right
	node = Node( key )
	node.parent, node.left, node.right, node.red = y, self._null, self._null, True
	if y == self._null:
	self.root = node
	elif node.key <= y.key:
	y.left = node
	else:
	y.right = node
	self._fixIns( node )
	def min( self, node = None ):
	""" find min from a given node """
	node = node if node else self.root
	while node.left.key:
	node = node.left
	return node.key
	def max( self, node = None ):
	""" find max from a given node """
	node = node if node else self.root
	while node.right.key:
	node = node.right
	return node.key
	def _fixIns( self, node ):
	""" fixtures after insertion """
	while node.parent.red:
	if node.parent == node.parent.parent.left:
	if node.parent.parent.right.red:
	node.parent.red = False
	node.parent.parent.right.red = False
	node.parent.parent.red = True
	node = node.parent.parent
	else:
	if node == node.parent.right:
	node = node.parent
	self.rol(node)
	node.parent.red = False
	node.parent.parent.red = True
	self.ror( node.parent.parent )
	else:
	if node.parent.parent.left.red:
	node.parent.red = False
	node.parent.parent.left.red = False
	node.parent.parent.red = True
	node = node.parent.parent
	else:
	if node == node.parent.left:
	node = node.parent
	self.ror(node)
	node.parent.red = False
	node.parent.parent.red = True
	self.rol( node.parent.parent )
	self.root.red = False
	def rol( self, x ):
	""" rotate left """
	if not x.key: return
	y = x.right
	x.right = y.left
	if y.left != self._null:
	y.left.parent = x
	y.parent = x.parent
	if x.parent == self._null:
	self.root = y
	elif x == x.parent.left:
	x.parent.left = y
	else:
	x.parent.right = y
	y.left = x
	x.parent = y
	def ror( self, y ):
	""" rotate right """
	if not y.key: return
	x = y.left
	y.left = x.right
	if x.right != self._null:
	x.right.parent = y
	x.parent = y.parent
	if y.parent == self._null:
	self.root = x
	elif y == y.parent.right:
	y.parent.right = x
	else:
	y.parent.left = x
	x.right = y
	y.parent = x
	def transplant( self, u, v ):
	""" transplant subtrees
	plant v in place of u
	"""
	if u.parent == self._null:
	self.root = v
	elif u == u.parent.left:
	u.parent.left = v
	else:
	u.parent.right = v
	v.parent = u.parent
	def find( self, k ):
	""" find for a key k """
	node = self.root
	while node != self._null and node.key != k:
	if k < node.key:
	node = node.left
	else:
	node = node.right
	return node
	def delete( self, z ):
	""" delete Node z """
	y = z
	zcol = y.red
	if z.left == self._null:
	x = z.right
	self.transplant( z, z.right )
	elif z.right == self._null:
	x = z.left
	self.transplant( z, z.left )
	elif y == self.min( z.right ):
	zcol = y.red
	x = y.right
	if y.parent == z:
	x.parent = y
	else:
	self.transplant( y, y.right )
	y.right = z.right
	y.right.parent = y
	self.transplant( z, y )
	y.left = z.left
	y.left.parent = y
	y.red = z.red
	if not zcol:
	self._fixDel( x )
	def _fixDel( self, x ):
	""" fixtures after deletion """
	while x != self.root and x.red:
	if x == x.parent.left:
	w = x.parent.right
	if w.red:
	w.red = False
	x.parent.red = True
	self.rol( x.parent )
	w = x.parent.right
	if not w.left.red and not w.right.red:
	w.red = True
	x = x.parent
	else:
	if not w.right.red:
	w.left.red = False
	w.red = True
	self.ror(w)
	w = x.parent.right
	w.red = x.parent.red
	x.parent.red = False
	w.right.red = False
	self.rol( x.parent )
	x = self.root
	else:
	w = x.parent.left
	if w.red:
	w.red = False
	x.parent.red = True
	self.ror( x.parent )
	w = x.parent.left
	if not w.left.red and not w.right.red:
	w.red = True
	x = x.parent
	else:
	if not w.left.red:
	w.right.red = False
	w.red = True
	self.rol(w)
	w = x.parent.left
	w.red = x.parent.red
	x.parent.red = False
	w.left.red = False
	self.ror( x.parent )
	x = self.root
	def dfs( self, node = None ):
	""" dummy inorder dfs to check """
	node = node if node else self.root
	if node.left.key:
	self.dfs( node.left )
	print node.key,
	if node.right.key:
	self.dfs( node.right )
	def dot( self, fname ):
	""" dummy dot file creation
	to generate pic run:
	neato -T png fname > fname.png
	or
	dot -T png fname > fname.png
	"""
	f = open( fname, "w+" )
	f.write( "digraph rb {\n")
	def nodeId( node ):
	return "node%s" % id(node)
	def nodeCol( node ):
	return "red" if node.red else "black"
	def visit( node, f ):
	f.write( '%s [label="%s",color="%s",shape="circle"];\n' % ( nodeId(node), node.key, nodeCol(node) ) )
	if node.left.key:
	visit( node.left, f )
	f.write( "%s -> %s;\n" % ( nodeId(node), nodeId(node.left) ) )
	if node.right.key:
	visit( node.right, f )
	f.write( "%s -> %s;\n" % ( nodeId(node), nodeId(node.right) ) )
	visit( self.root, f )
	f.write( "}\n" )
	f.close()
	# # just for fun make some dot
	if __name__ == "__main__":
	t = rbTree()
	x = range(500)
	import random
	random.shuffle( x )
	for i in x:
	t.insert( i )
	t.dot( "rb500.dot")

view raw rbTree.py hosted with ❤ by GitHub

:)

python popcnt

popcnt - count bits set ("1") in a integer, of course using python

I've implemented only four ways to do this:

• using look up table 0..255 (no iterations, oen sum and a few shifting by 8 bits)
• naive (number of iterations ==  number of bits)
• Brian Kernighan way (number of iterations == number of bits set)
• pythonic by ugly (count "1"s after calling bin()...)

	#!/bin/env python
	""" :mod: popcnt
	============
	.. module: popcnt
	:synopsis: couting bits set ("1") in int or long
	.. moduleauthor:: Krzysztof.Ciba@NOSPAMgmail.com
	"""
	## bit count look up table in range 0..255
	__bcLUT = [ 0 ] * 256
	for i in range(256):
	__bcLUT[i] = ( i & 1 ) + __bcLUT[i/2]
	def popcntLUT( arg ):
	""" popcnt using look up table """
	assert type(arg) in ( int, long )
	e = lambda x, y: x + int( bool( y ) ) << 3
	return sum( [ __bcLUT[ ( arg >> i ) & 255 ]
	for i in range( 0, e( *divmod( arg.bit_length(), 8) ), 8 ) ] )
	def popcntBK( arg ):
	""" Brian Kernighan way - loop only for bits set """
	assert type(arg) in ( int, long )
	pop = 0
	while arg:
	arg &= arg - 1
	pop += 1
	return pop
	def popcntNaive( arg ):
	""" naive - loop for every bit in arg """
	assert type(arg) in ( int, long )
	pop = 0
	while arg:
	pop += arg & 1
	arg >>= 1
	return pop
	def popcntUgly( arg ):
	""" ugly but pythonic way? """
	assert type(arg) in ( int, long )
	return bin(arg).count("1")
	# # eep!
	if __name__ == "__main__":
	# dummy testing
	for i in range(1024):
	ugly = popcntUgly(i)
	lut = popcntLUT(i)
	bk = popcntBK(i)
	naive = popcntNaive(i)
	assert ugly == lut
	assert ugly == bk
	assert ugly == naive

view raw popcnt.py hosted with ❤ by GitHub

All function were run on 1000 samples made by 100 random numbers:

	# --- testBK.py
	import sys
	import random
	from popcnt import popcntBK
	up = 2**256
	for i in range(1, 1001):
	if not i % 10:
	print ".",
	sys.stdout.flush()
	if not i % 100:
	print
	sys.stdout.flush()
	for j in range(1000):
	popcntBK( random.randint( 0, up ) )
	# --- testLUT.py
	import sys
	import random
	from popcnt import popcntLUT
	up = 2**256
	for i in range(1, 1001):
	if not i % 10:
	print ".",
	sys.stdout.flush()
	if not i % 100:
	print
	sys.stdout.flush()
	for j in range(1000):
	popcntLUT( random.randint( 0, up ) )
	# --- testNaive.py
	import sys
	import random
	from popcnt import popcntNaive
	up = 2**256
	for i in range(1, 1001):
	if not i % 10:
	print ".",
	sys.stdout.flush()
	if not i % 100:
	print
	sys.stdout.flush()
	for j in range(1000):
	popcntNaive( random.randint( 0, up ) )
	# --- testUgly.py
	import sys
	import random
	from popcnt import popcntUgly
	up = 2**256
	for i in range(1, 1001):
	if not i % 10:
	print ".",
	sys.stdout.flush()
	if not i % 100:
	print
	sys.stdout.flush()
	for j in range(1000):
	popcntUgly( random.randint( 0, up ) )

view raw gistfile1.py hosted with ❤ by GitHub

And now testing results:

• naive (Zzzzz...)

[Wed, 05 Jun 22:07 E0][cibak@localhost:~/popcnt]> time python testNaive.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
175.885u 0.055s 2:56.35 99.7%    0+0k 0+0io 0pf+0w

• BK way (much better!)

[Wed, 05 Jun 22:04 E0][cibak@localhost:~/popcnt]> time python testBK.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
75.853u 0.028s 1:16.03 99.7%    0+0k 0+0io 0pf+0w 

• look up table (niiiice!)

[Wed, 05 Jun 22:06 E0][cibak@localhost:~/popcnt]> time python testLUT.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
42.828u 0.030s 0:42.93 99.8%    0+0k 0+0io 0pf+0w 

• ugly but pythonic (wut?)

[Wed, 05 Jun 22:04 E1][cibak@localhost:~/popcnt]> time python testUgly.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
40.880u 0.040s 0:41.06 99.6%    0+0k 0+0io 0pf+0w


And guess what? Ugly (but pythonic) won! Coincidence? I don't think so... ;)

EDIT:
And of course I can completely remove lines with lambda and all this stuff within popcntLUT  and it could be coded just like that:

	## bit count look up table in range 0..255
	__bcLUT = [ 0 ] * 256
	for i in range(256):
	__bcLUT[i] = ( i & 1 ) + __bcLUT[i/2]
	def popcntLUT( arg ):
	""" popcnt using look up table """
	assert type(arg) in ( int, long )
	return sum( [ __bcLUT[ ( arg >> i ) & 255 ]
	for i in range( 0, arg.bit_length(), 8 ) ] )

view raw popcntLUT.py hosted with ❤ by GitHub

But it doesn't help to much.

Also one can check say 16 bits look up table, say:

	__bc16b = [ 0 ] * (256*256)
	for i in range(256*256):
	__bc16b[i] = ( i & 1 ) + __bc16b[i/2]
	def popcnt16b( arg ):
	""" popcnt using 16bits loom up table """
	return sum( [ __bc16b[( arg >> i ) & 65535 ] for i in range( 0, arg.bit_length(), 16 ) ] )

view raw popcnt16b.py hosted with ❤ by GitHub

 This should run at least 2 times faster that original popcntLUT.

 

one does not simply pickle a tree

Ahrrr... It took me 5 hours to figure it out.

Python multiprocessing.Queue is using internally shelve module, which again internally is using cPickle for speed up.  But if something cannot be pickled, when calling Queue.put, you will see some cryptic error message:


File "/opt/dirac/pro/Linux_x86_64_glibc-2.5/lib/python2.6/multiprocessing/queues.py", line 242, in _feed
-    send(obj)
TypeError: expected string or Unicode object, NoneType found

Ugh! Not helping at all, but what to do except start debugging? Taking the advantage of the opportunity I had fixed also some problems here and there (un-shelvable locks or instance methods in several classes), but at the very, very end  I've got this:

pickle.PicklingError: Can't pickle : it's not found as __main__.copyelement

 Huh? What the heck? Where is this one? Find and grep fellows stayed completely  muted, so I've started to dump symbols from *.so under PYTHONPATH, and guess what? I HAVE FOUND IT!

[volhcb13] /opt/dirac/pro > nm Linux_x86_64_glibc-2.5/lib/python2.6/lib-dynload/_elementtree.so | grep copyelement
0000000000209dd8 b elementtree_copyelement_obj



This little bastard was hiding in cElementTree! I've swapped this one with its  python twin (ElementTree). Taa-daam!  Queue.put is working again, not a big deal for me,  XML fragments I'm dealing with are rather small.

5 hours! Five! FIVE HOURS lost...

So, dear children, please remember: when going multiprocessing forget about cElementTree (and perhaps several other modules rewritten in C for speed up) and use pure python implementations.

nth permutation in a lexicographical order

Problem:

Somebody is generating permutations of a given list of elements in a lexicographical order. What is the value of say nth permutation?

Brute force solution is to generate them all, but in that case you'll spend quite a lot of time generating useless permutations - O(n!). So here is the easy way:

	#!/bin/env python
	"""
	Solves a problem of getting permutation of a given index,
	while you know that permutations are created in a lexicographical order.
	As input you are specifying a list of elements and index of permutation you want to get.
	"""
	## imports
	from math import factorial
	## this one just for checking
	from itertools import permutations
	def getNthPermutation( pIndex, inList, outList=[] ):
	""" get :pIndex: permutation of :inList:
	:warn: permutations are sorted in lexicographical order starting from 0, i.e.:
	0 -> [1, 2, 3], 1 -> [1, 3, 2] and so on
	:param int pIndex: given permutation index
	:param list inList: initial list of elements
	:param list outList: result list
	"""
	## permutation index too big
	if pIndex >= factorial( len(inList) ): return []
	## no more elements to use
	if not inList: return outList
	## make sure eList is sorted
	inList.sort()
	## get factorial
	f = factorial( len(inList)-1 )
	index = pIndex / f
	reminder = pIndex % f
	## add new element to outList
	outList.append( inList[index] )
	## ...and remove it from inList
	del inList[index]
	## bail out or call recursively depending of the reminder
	if not reminder:
	return outList + inList
	else:
	return getNthPermutation( reminder, inList, outList )
	### test execution
	if __name__ == "__main__":
	ps = permutations( [1,2,3,4,5,6] )
	for i in range(factorial(6)):
	resList = []
	res = getNthPermutation( i, [1,2,3,4,5,6], resList )
	check = list( ps.next() )
	assert( res == check )

view raw perm.py hosted with ❤ by GitHub