for l in open(filename):
fields = [int(f) for f in l.split()]
vertex = fields.pop(0)
incident = [tuple(sorted([vertex, f])) for f in fields]
vertices.append(vertex)
edges.update(incident)
return vertices, list(edges)
def RandomContraction(vertices, edges):
while len(vertices) > 2:
edge = random.choice(edges)
a, b = edge
vertices.remove(b)
new_edges = []
for e in edges:
if e == edge:
continue
if b in e:
if e[0] == b:
other = e[1]
if e[1] == b:
other = e[0]
e = tuple(sorted([a, other]))
new_edges.append(e)
edges = new_edges
return vertices, edges
vertices, edges = ParseGraph(sys.argv[1])
minimum = sys.maxint
for i in range(0, 1000):
v, e = RandomContraction(vertices[:], edges[:])
print v, len(e)
if len(e) < minimum:
minimum = len(e)
#load the array with text file
fin = open(../../coresera/inversions/IntegerArray.txt)
A=[]
for line in fin:
A.append(int(line.strip()))
mearge sort : python code
import random
from sys import maxsize as inf
def merge_sort(A): def merge(L, R): m = len(L)-1 B = [] i = j = 0 inv = 0 while L[i] != inf or R[j] != inf: if L[i] <= R[j]: B.append(L[i]) i += 1 else: B.append(R[j]) inv += m - i j += 1 return B, inv n = len(A) inv = 0 if n >= 2: mid = n // 2 L, R = A[:mid], A[mid:] L, inv_left = merge_sort(L) R, inv_right = merge_sort(R) A, inv_split = merge(L + [inf], R + [inf]) inv = inv_left + inv_right + inv_split return A, inv
if __name__ == '__main__': A = [1,6,3,2,4,5] A, inv = merge_sort(A) print (inv) print (A)
# Count the number of lines in a file.
if __name__ == "__main__":
in_file = open("../../coresera/inversions/IntegerArray.txt")
line_count = 0
while True:
in_line = in_file.readline().strip()
if in_line == "":
break;
line_count += 1
in_file.close()
print("Line count:", line_count)
Ādityahṛdayam is a hymn associated with Aditya or the Sun God and was recited by the sage Agastya to Rama on the battlefield before fighting with Ravana. This historic hymn starts at the beginning of the duel between Rama and Ravana. Agastya teaches Rama, who is fatigued after the long battle with various warriors of Lanka, the procedure of worshiping the Sun god for strength to defeat the enemy. These verses belong to Yuddha Khanda , in the Ramayana as composed by Valmiki.
