Code to form a set from a list of element pairs in java

Question

Say I have a list of pair of elements like (1, 2) (3, 4) where no duplicates are present and for a pair (p, q) p != q. How to form a set from this elements using simple code (I do not intend to use a data structure like disjoint set and unions but java library APIs - unless the code can be written in a simple fashion). Example: (1, 2) (2, 4) (5, 6) (4, 7) (3, 5) should output: {1, 2, 4, 7} and {3, 5, 6}

    List<Set<Integer>> list = new ArrayList<>();
    for(String s : pairs){
        String[] values = s.split(" ");
        Integer val1 = Integer.parseInt(values[0]);
        Integer val2 = Integer.parseInt(values[1]);

        Set<Integer> pairSet = new HashSet<>();
        pairSet.add(val1);
        pairSet.add(val2);

        boolean exists = false;
        for(Set<Integer> set : list){
            if(set.contains(val1) || set.contains(val2)) {
                set.addAll(pairSet);
                exists = true;
                break;
            }
        }
        if(!exists)
            list.add(pairSet);
    }

This is a naive approach which is incorrect. If I get a sequence (1 2) (3 4) and (2 3) then the output becomes {1, 2, 3} and {3, 4}.

This happens because the list of sets gets created like this: {1, 2} and then {3, 4} then when the pair (2 3) comes, it DOES NOT merge the 2 sets.

I can write a code to check the first value is present in any set say S1 and then same for the other value say S2 and then merge:

    //loop -> s1 = find val1
    //loop -> s2 = find val2
    if s1 != null and s2 != null //merge s1 and s2
    if(s1 == null && s2 != null) //add val1 and val2 to s2
    if(s1 != null && s2 == null) //add val1 and val2 to s1
    if(both null) create a new set of val1 and val2

Too many loops and conditions. Any simpler solution?

Answer 1

I am posting a solution. If someone can make this code simpler it would be great. TIA

        static void formSet(String[] pairs) {

    List<Set<Integer>> list = new ArrayList<>();
    for(String s : pairs){
        String[] values = s.split(" ");
        Integer val1 = Integer.parseInt(values[0]);
        Integer val2 = Integer.parseInt(values[1]);

        Set<Integer> pairSet = new HashSet<>();
        pairSet.add(val1);
        pairSet.add(val2);

        Set<Integer> val1_set = null, val2_set = null;
        for(Set<Integer> set : list){
            if(set.contains(val1)) {
                val1_set = set;
            }

            if(set.contains(val2)) {
                val2_set = set;
            }
        }
        if(val1_set == null && val2_set == null)
            list.add(pairSet);
        if(val1_set != null && val2_set == null)
            val1_set.addAll(pairSet);
        if(val1_set == null && val2_set != null)
            val2_set.addAll(pairSet);
        if(val1_set != null && val2_set != null){
            list.remove(val2_set);
            val1_set.addAll(val2_set);
        }
    }

    for(Set<Integer> set : list){
        System.out.println(set);
    }
}

here's a link to codereview: https://codereview.stackexchange.com/questions/163301/forming-a-set-from-a-pair-of-numbers

Answer 2

A simple DFS would do the trick if you consider each pair as a description of an edge of a graph.

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution
{
  static int n = 1000000;
  static ArrayList< ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer>>();
  static Boolean[] visited = new Boolean[n];

public static void main (String[] args) throws java.lang.Exception
{
    String input[] = {"1 2", "3 4", "2 3","5 6"};
    System.out.println(answer(input));
}

public static void dfs(int u,Set<Integer> res){
    visited[u] = true;
    for(int e : adj.get(u)){
        if(!visited[e])
             dfs(e,res);
    }
    res.add(u);
}
static void init(){
    for(int i = 0 ; i < n ; i++)
        adj.add(new ArrayList<Integer>());
}

public static List<Set<Integer>> answer(String[] pairs){
    init();
    List<Set<Integer>> list = new LinkedList<>();
    Set<Integer> elements = new HashSet<Integer>();
    for(int i = 0 ; i < pairs.length ; i++){
    String[] splitted = pairs[i].split(" ");
     int u = Integer.parseInt(splitted[0]);
     int v = Integer.parseInt(splitted[1]);
        adj.get(u).add(v);
        adj.get(v).add(u);
        visited[u] = visited[v] = false;
        elements.add(u);elements.add(v);
    }

    for(int e : elements){
        if(!visited[e]){
            Set<Integer> tmp = new HashSet<Integer>();
            dfs(e,tmp);
            list.add(tmp);
        }
    }
    return list;
}
}

Answer 3

Revised version:

Here, I have made it using what you referred to as Naive approach:

public static List<Set<Integer>> answer(String[] pairs){

    List<Set<Integer>> list = new LinkedList<>();
    // For each pair, separate the numbers
    //Initialize with initial set
    Set<Integer> init = new HashSet<>();
    String[] splitted = pairs[0].split(" ");
    init.add(Integer.parseInt(splitted[0]));
    init.add(Integer.parseInt(splitted[1]));

    list.add(init);

    // To be used to maintain set record ahead
    List<Set<Integer>> setsRecord = new LinkedList<>();

    boolean found = false;
    Integer i1, i2;
    for(String s : pairs){
        i1 = Integer.parseInt((splitted = s.split(" "))[0]);
        i2 = i2 = Integer.parseInt(splitted[1]);
        for(Set<Integer> set : list){
            if(set.contains(i1) || set.contains(i2)){
                // If element has already been found in a set, create a common set
                if(setsRecord.size() >= 1){
                    setsRecord.get(0).addAll(set);
                    // And remove this set
                    list.remove(set);
                }
                else{
                    set.add(i1);
                    set.add(i2);
                    // Maintain a record of this set
                    setsRecord.add(set);
                }
                found = true;
            }
        }
        // Empty the temporary set record
        setsRecord.clear();

        if(!found){
            Set<Integer> newSet = new HashSet<Integer>();
            newSet.add(i1);
            newSet.add(i2);
            list.add(newSet);
        }
        found = false;
    }
    return list;
}

Demo.