143269498 function calls in 185.193 seconds

Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1   47.656   47.656  183.583  183.583 ex2_big.py:18(cluster_alg)
        1    1.090    1.090  185.193  185.193 ex2_big.py:2(<module>)
  192670    0.165    0.000    0.165    0.000 ex2_big.py:39(union)
 11247652   13.388    0.000   13.388    0.000 ex2_big.py:49(find)
110327340  120.790    0.000  122.365    0.000 ex2_big.py:5(all_string_with_diff)
 14511524    1.175    0.000    1.175    0.000 ex2_big.py:6(<genexpr>)
  5000000    0.355    0.000    0.355    0.000 ex2_big.py:61(<genexpr>)
   596364    0.044    0.000    0.044    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.010    0.005    0.010    0.005 {method 'keys' of 'dict' objects}
   200001    0.144    0.000    0.144    0.000 {method 'split' of 'str' objects}
   200001    0.020    0.000    0.020    0.000 {method 'strip' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {open}
   993940    0.355    0.000    0.355    0.000 {range}

def all_string_with_diff(tup,k):
    perms = [(j for j in range(i-1,len(tup)-k+i))for i in range(1,k+1)]
    for x in product(*perms):
        l = list(tup)
        for y in x:
            if l[y] =='1':
                l[y] = '0'
            else:
                l[y] = '1'
        yield tuple(l)

import sys
from itertools import product

def all_string_with_diff(tup,k):
    li = list
    tu = tuple
    perms = [(j for j in range(i-1,len(tup)-k+i))for i in range(1,k+1)]
    for x in product(*perms):
        l = li(tup)
        for y in x:
            if l[y] =='1':
                l[y] = '0'
            else:
                l[y] = '1'
        yield tu(l)



def cluster_alg(nodes,n):
    d = 1
    i = 0
    while d<3:
        for n1 in nodes.keys():
            i = i+1
            if i%1000 ==0:
                print(d,i)
            for n2 in all_string_with_diff(n1,d):
                if n2 in nodes:
                    r1 = find(nodes,n1)
                    r2 = find(nodes,n2)
                    if r1 != r2:
                        union(nodes, r1, r2)
                        n = n-1
        d = d+1
    return n




def union(clusters, r1, r2):
    r1 = clusters[r1]
    r2 = clusters[r2]
    if r1[1]>= r2[1]:
        r2[0] = r1[0]
        r1[1] = r1[1] + r2[1]
    else:
        r1[0] = r2[0]
        r2[1] = r2[1] + r1[1]

def find(clusters, u):
    while clusters[u][0]!= u:
        u = clusters[u][0]
    return u

nodes = {}
n = 0
for index, line in enumerate(open(sys.argv[1], 'r')):
    if index==0:
        node_data = line.strip().split(" ")
        n = int(node_data[0])
    else:
        arr = tuple(i for i in line.strip().split(" "))
        if arr in nodes:
            n = n-1
        else:
            nodes[arr] = [arr,1]


print(cluster_alg(nodes,n))