Equality in Set<Set> Java

Question

I have a method that returns Set<Set<String>>. In my test, I am trying to check if the expected Sets are present using contains() method.

eg. input = "cat", "dog", "god"

output = [[cat], [dog, god]]

Now, if I do output.contains(new HashSet<>(Arrays.asList("cat"))) it returns true.

But if I do output.contains(new HashSet<>(Arrays.asList("dog", "god"))) it returns false.

According to my understanding, it should return true in both cases.

What am I missing here?

public class AnagramGroups {
     public Set<Set<String>> group(Set<String> words) {
         Set<Set<String>> groups = new HashSet<>();
         for(String word: words) {
             findAndAdd(word, groups);
         }
         return groups;
     }

     private void findAndAdd(String word, Set<Set<String>> groups) {
         for(Set<String> group: groups) {
             boolean found = false;
             for(String str: group) {
                 if(isAnagram(str, word)) {
                     found = true;
                 }
                 break;
             }
             if(found) {
                 group.add(word);
                 return;
             }
         }
         Set<String> set = new HashSet<>();
         set.add(word);
         groups.add(set);
     }

     private boolean isAnagram(String str, String word) {
         Set<Character> characters = new HashSet<>();
         for(char c: str.toCharArray()) {
             characters.add(c);
         }
         for(char c: word.toCharArray()) {
             if(!characters.contains(c)) {
                 return false;
             }
             characters.remove(c);
         }
         return characters.isEmpty();
     }

     public static void main(String[] args) {
         Set<Set<String>> groups = new AnagramGroups()
             .group(new HashSet<>(Arrays.asList("cat", "god", "dog")));
         System.out.println(groups);

         Set set1 = new HashSet<>(Arrays.asList("cat"));
         Set set2 = new HashSet<>(Arrays.asList("god", "dog"));
         System.out.println(groups.contains(set1));
         System.out.println(groups.contains(set2));

         groups.add(new HashSet<>(Arrays.asList("god", "dog")));
         System.out.println(groups);
     }
}

Adrianadriana

Answer 1

The issue is in your findAndAdd method, where you are mutating an element (group) of the outer Set (groups), therefore changing its hashCode(). As a result, groups.contains(set2) cannot find a Set that is present in groups, since it looks for it in the wrong bucket (matching the new hashCode()) instead of the bucket to which it was added (matching the original hashCode()).

You can fix your code by removing the group Set from groups before mutating it and then re-add it.

Change your code from:

 private void findAndAdd(String word, Set<Set<String>> groups) {
     for(Set<String> group: groups) {
         boolean found = false;
         for(String str: group) {
             if(isAnagram(str, word)) {
                 found = true;
             }
             break;
         }
         if(found) {
             group.add(word);
             return;
         }
     }
     Set<String> set = new HashSet<>();
     set.add(word);
     groups.add(set);
 }

to:

 private void findAndAdd(String word, Set<Set<String>> groups) {
     for(Set<String> group: groups) {
         boolean found = false;
         for(String str: group) {
             if(isAnagram(str, word)) {
                 found = true;
             }
             break;
         }
         if(found) {
             groups.remove(group);
             group.add (word);
             groups.add(group);
             return;
         }
     }
     Set<String> set = new HashSet<>();
     set.add(word);
     groups.add(set);
 }

When I tried your code and made that change, I got true in both cases.

Output:

[[cat], [god, dog]]
true
true
[[cat], [god, dog]]

Fideism

@Fideism Thank you so much! – Adrianadriana

Answer 2

When you use Set set2 = new HashSet<>(Arrays.asList("god", "dog")); You are not checking for a combination "god" and "dog", but you check for each element god then dog exist in your Set<Set<String>> or not, and in your set you have only one element cat is separated. it is like :

groups contains `god` -> no
groups contains `dog` -> no

return false

To solve your problem you can use equals like so :

groups.stream().anyMatch(a -> a.equals(set2))// or groups.stream().anyMatch(set2::equals)

or

groups.stream().anyMatch(a -> a.containsAll(set2))

Allocate

The Set created by new HashSet<>(Arrays.asList("cat", "god", "dog")) is not the Set on which groups.contains(set2) is called. groups is generated by the AnagramGroups, which groups the "dog" and "god" Strings in the same inner Set. – Fideism

Answer 3

Try this.

static String sort(String s) {
    int[] sortedCP = s.codePoints().sorted().toArray();
    return new String(sortedCP, 0, sortedCP.length);
}

public static Set<Set<String>> group(Set<String> words) {
    Map<String, Set<String>> map = new HashMap<>();
    for (String word : words)
        map.computeIfAbsent(sort(word), k -> new HashSet<>()).add(word);
    return new HashSet<>(map.values());
}

And

Set<String> words = new HashSet<>(Arrays.asList("cat", "dog", "god"));
System.out.println(group(words));

result:

[[cat], [god, dog]]

Intermediate variable map has

{act=[cat], dgo=[god, dog]}

Taler