How to check whether two sequences have the same values in some order, (ignoring duplicates) java

Question

This is a 2 part question 1st the question asks to create a method to check whether two sequences have the same values in the same order.

Secondly the bit I'm stuck on the question asks to create a method to check whether two sequences have the same values in some order, ignoring duplicates ie Sequence 1 (1, 4, 9, 16, 9, 7, 4, 9, 11) Sequence 2 (11, 11, 7, 9, 16, 4, 1) So sequence 1 would still be identical with sequence 2 as 11, 4, and 9 are duplicate elements

So I added a method public boolean equals(Sequence other) that checks whether the two sequences have the same values in the same order part 1, but what I need to do now is part 2 check whether two sequences have the same values in some order, ignoring duplicates.

import java.util.Arrays;
public class Sequence {
    private int[] values;
    public Sequence(int size)
    {
        values = new int[size];
    }
    public void set(int i, int n)
    { 
        values[i] = n; 
    }
    public boolean equals(Sequence obj) 
    {
        if (this == obj)
        {
            return true;
        }
        if (obj == null)
        {
            return false;
        }
        if (getClass() != obj.getClass())
        {
            return false;
        }
        Sequence other = (Sequence) obj;
        if (!Arrays.equals(values, other.values))
        {
            return false;
        }
        return true;
    }
    public static void main(String args[]){
        Sequence s = new Sequence(5);
        Sequence s2 = new Sequence(5);// new Sequence(4)
        s.set(0, 1);
        s2.set(0, 1);
        System.out.println(s.equals(s2));//will print true      
    }
}

I'm a little confused I know this is how you check duplicates but that is all I know I don't really know how use it in this scenario or how to ignore duplicates

for (int i = 0; i < values.length; i++) 
{ 
    for (int j = i + 1; j < other.length; j++) 
    { 
        if (values[i].equals(other[j]) ) {}
    }
}

Answer 1

The slow approach is: walk the smaller array, and for each value, check if it is contained in the larger one. And then the other way round... So, without any further "smarts" you need to go for n * m comparisons. Times 2.

A more sophisticated solution: sort both arrays. Then start walking both arrays in turns (when both arrays are sorted, you don't need to iterate the second array repeatedly to figure if it contains a value from the other array). Then you only need to walk through both arrays once (but as said: in some alternating fashion).

Answer 2

I think the easiest approach will be the following:

• Sort the two arrays
  
• Get the distinct values of the arrays.
• Compare the sorted, unique arrays

Update, with thanks to @DodgyCodeException, it turns out it is more efficient to sort the array within the streams.

    int[] val1 = {1,1,4,9,16,9,7,4,9,11};
    int[] val2 = {11, 7, 9, 16, 7, 4, 1};

    //Compare should  be false
    System.out.println(Arrays.equals(val1, val2)); //false

    //Sort Array and get distinct Values
    //Assign to new int[] if you do not want to change the original arrays
    val1 = Arrays.stream(val1).sorted().distinct().toArray();
    val2 = Arrays.stream(val2).sorted().distinct().toArray();

    //Compare should be true
    System.out.println(Arrays.equals(val1, val2)); //true

Answer 3

This is trivial with Java's Set mechanics. The following snippet will work as long as equals and hashCode are implemented correctly for type T:

private boolean equalWithDuplicates(T[] a, T[] b) {
    return new HashSet<>(Arrays.asList(a)).equals(new HashSet<>(Arrays.asList(b)));
}

However, as a commenter points out, this SO post seems to indicate arrays of primitives need to be boxed for the solution to work:

private boolean equalWithDuplicates(int[] a, int[] b) {
    Set<Integer> boxedA = Arrays.stream(a).boxed().collect(Collectors.toSet());
    Set<Integer> boxedB = Arrays.stream(b).boxed().collect(Collectors.toSet());
    return boxedA.equals(boxedB);
}

Answer 4

Not sure what you mean, but if you want to remove duplicates, the easiest thing is to use a java.util.Set, like java.util.HashSet. Further, writing an equals(Sequence obj)-method could be considered bad practice, since it overloads the equals(Object obj).You probably want to overwrite that method, rahter then overload it.

Answer 5

I think your Sequence class could look like this one. The main idea for EQUALS_IGNORE_ORDER_AND_DUPLICATES is just transform input data to data, that could be use with equal function that you're already created.

final class Sequence {

    private final int[] values;

    public Sequence(int size) {
        values = new int[size];
    }

    public void set(int i, int n) {
        values[i] = n;
    }

    public static final BiPredicate<Sequence, Sequence> EQUALS = (seq1, seq2) -> Arrays.equals(seq1.values, seq2.values);

    public static final BiPredicate<Sequence, Sequence> EQUALS_IGNORE_ORDER_AND_DUPLICATES = (seq1, seq2) -> {
        Set<Integer> set1 = seq1 != null ? Arrays.stream(seq1.values).boxed().collect(Collectors.toSet()) : Collections.emptySet();
        Set<Integer> set2 = seq2 != null ? Arrays.stream(seq2.values).boxed().collect(Collectors.toSet()) : Collections.emptySet();
        return set1.equals(set2);
    };

}

Test:

int[] val1 = { 1, 1, 4, 9, 16, 9, 7, 4, 9, 11 };
int[] val2 = { 11, 7, 9, 16, 7, 4, 1 };

Sequence seq1 = new Sequence(val1.length);
Sequence seq2 = new Sequence(val2.length);

for (int i = 0; i < val1.length; i++)
    seq1.set(i, val1[i]);

for (int i = 0; i < val2.length; i++)
    seq2.set(i, val2[i]);

boolean res1 = Sequence.EQUALS.test(seq1, seq2);    // false
boolean res2 = Sequence.EQUALS_IGNORE_ORDER_AND_DUPLICATES.test(seq1, seq2);   // true