Forming sets from pairs of numbers

Question

I do not want to use a new data structure but the existing APIs in Java. Here's a solution. I am thinking if this can be made simpler. Input say {"1 2", "4 3", "5 5", "2 3"} and output is [1, 2, 3, 4] [5]

    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);
    }
}

Answer 1

First and foremost : your code contains a subtle bug. Try this input : {"1 2", "4 3", "5 5", "2 3", "1 3"}

As for style;

• please respect standard naming conventions.
• seperate concerns : parsing the string into a pair should be done in a separate method, this will improve readability.
• it's unclear from just looking at your code what the algorithm does exactly. Try finding a better name for the method and certain variables. If that's insufficient, some documentation can also help.
• probably this is an exercise, as your algorithm simply prints its result, rather than return it. But generally such methods are useless, plus it mingles concerns again. Make the method return its result, and make a client method print the result. The main method would then call three methods



List<Set<Integer>> pairs = parse(input);
List<Set<Integer>> clusters = calculateClusters(pairs);
print(clusters);

Answer 2

Your implementation is good. One thing I would change, I would add else before all but first if where you are comparing val_set against null, as e.g. if val1_set == null && val2_set == null, it wouldn't go to the next check of val1_set != null && val2_set == null, but skip to next loop.

if (...)
    ...
else if (...)
    ...

Alternative approach to the problem could be storing the edges you are given, and only after going through all input, traverse those edges and collect nodes that have a path between into sets. Is the solution simpler however? I don't know, probably not.

void makesets(String[] pairs) {
        //edges of the graph
        Map<Integer, Set<Integer>> connections = new HashMap<>();
        for (String pair : pairs) {
            Integer nr[] = Arrays.stream(pair.split(" "))
                .map(s -> Integer.parseInt(s))
                .toArray(Integer[]::new);
            for (int i = 0; i < 2; i++) {
                if (connections.get(nr[i]) == null)
                    connections.put(nr[i], new HashSet<>());
                connections.get(nr[i]).add(nr[1 - i]);
            }
        }
        Set<Integer> traversed = new HashSet<>();
        List<Set<Integer>> list = new ArrayList<>();
        for (Integer node : connections.keySet()) {
            if (traversed.contains(node)) continue;
            Set<Integer> set = new HashSet<>();
            collectSet(node, connections, set);
            list.add(set);
            traversed.addAll(set);
        }
        for(Set<Integer> set : list){
            System.out.println(set);
        }
    }

    void collectSet(Integer node, Map<Integer, Set<Integer>> connections, Set<Integer> collected){
        if (collected.add(node)) {
            connections.get(node).forEach(n -> collectSet(n, connections, collected));
        }
    }