Created
July 28, 2018 18:13
-
-
Save viniru/24df0793d51c8e37d2f68602067e2fcd to your computer and use it in GitHub Desktop.
Clustering problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
import java.io.File; | |
public class ClusterB { | |
int n; | |
int bitsn; | |
int clusters ; | |
HashMap<String,Nodes> cl = new HashMap<>(); | |
void getInput() { | |
try { | |
File f = new File("C:\\Users\\vinir_000\\IdeaProjects\\Learn\\src\\input.txt"); | |
Scanner sc = new Scanner(f); | |
//Scanner sc = new Scanner(System.in); | |
n = sc.nextInt(); | |
bitsn = sc.nextInt(); | |
clusters = n; | |
sc.nextLine(); | |
for (int i = 0; i < n; i++) { | |
String s = sc.nextLine().replaceAll("\\s+", ""); | |
if (!cl.containsKey(s)) { | |
Nodes n = new Nodes(s); | |
cl.put(s, n); | |
} | |
//else System.out.println("I am present man"); | |
} | |
clusters = cl.size(); | |
} | |
catch(Exception e){} | |
} | |
void compute() | |
{ | |
//generate all the nodes at distances 1 | |
for(String s : cl.keySet()) | |
{ | |
for(int i=0;i<bitsn;i++ ) | |
{ | |
StringBuilder x = new StringBuilder(s); | |
if(x.charAt(i) == '1' ) | |
x.setCharAt(i,'0'); | |
else | |
x.setCharAt(i,'1'); | |
String y = new String(x.toString()); | |
merge(s,y); | |
} | |
} | |
//generate all the nodes at distances 2 | |
for(String s : cl.keySet()) | |
{ | |
for(int i=0;i<bitsn-1;i++ ) | |
{ | |
for(int j=i+1;j<bitsn;j++) | |
{ | |
StringBuilder x = new StringBuilder(s); | |
if (x.charAt(i) == '1') | |
x.setCharAt(i, '0'); | |
else | |
x.setCharAt(i, '1'); | |
if (x.charAt(j) == '1') | |
x.setCharAt(j, '0'); | |
else | |
x.setCharAt(j, '1'); | |
String y = new String(x.toString()); | |
merge(s, y); | |
} | |
} | |
} | |
} | |
void merge(String x,String y) | |
{ | |
if(cl.containsKey(y)) | |
{ | |
Nodes xp = getParent(x); | |
Nodes yp = getParent(y); | |
if(xp != yp) { | |
int xr = xp.rank; | |
int yr = yp.rank; | |
if (xr > yr) | |
yp.parent = xp; | |
else if (xr < yr) | |
xp.parent = yp; | |
else { | |
yp.parent = xp; | |
xp.rank = xp.rank + 1; | |
} | |
clusters--; | |
} | |
//System.out.println(clusters); | |
} | |
} | |
Nodes getParent(String x) | |
{ | |
if(cl.get(x).parent == cl.get(x)) | |
return cl.get(x); | |
cl.get(x).parent = getParent(cl.get(x).parent.s); | |
return cl.get(x).parent; | |
} | |
public static void main(String args[]) { | |
ClusterB cb = new ClusterB(); | |
cb.getInput(); | |
cb.compute(); | |
System.out.print(cb.clusters); | |
} | |
} | |
class Nodes | |
{ | |
String s; | |
Nodes parent ; | |
int rank = 0; | |
Nodes(String s) | |
{ | |
rank = 0; | |
this.s = s; | |
parent = this; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment