I have two ArrayLists of type Answer (self-made class).
I'd like to compare the two lists to see if they contain the same contents, but without order mattering.
Example:
//These should be equal.
ArrayList<String> listA = {"a", "b", "c"}
ArrayList<String> listB = {"b", "c", "a"}
List.equals states that two lists are equal if they contain the same size, contents, and order of elements. I want the same thing, but without order mattering.
Is there a simple way to do this? Or will I need to do a nested for loop, and manually check each index of both lists?
Note: I can't change them from ArrayList to another type of list, they need to remain that.
In that case lists {"a", "b"} and {"b","a"} are equal. And {"a", "b"} and {"b","a","c"} are not equal. If you use list of complex objects, remember to override equals method, as containsAll uses it inside.
if (oneList.size() == secondList.size() && oneList.containsAll(secondList)){
areEqual = true;
}
I had this same problem and came up with a different solution. This one also works when duplicates are involved:
public static boolean equalsWithoutOrder(List<?> fst, List<?> snd){
if(fst != null && snd != null){
if(fst.size() == snd.size()){
// create copied lists so the original list is not modified
List<?> cfst = new ArrayList<Object>(fst);
List<?> csnd = new ArrayList<Object>(snd);
Iterator<?> ifst = cfst.iterator();
boolean foundEqualObject;
while( ifst.hasNext() ){
Iterator<?> isnd = csnd.iterator();
foundEqualObject = false;
while( isnd.hasNext() ){
if( ifst.next().equals(isnd.next()) ){
ifst.remove();
isnd.remove();
foundEqualObject = true;
break;
}
}
if( !foundEqualObject ){
// fail early
break;
}
}
if(cfst.isEmpty()){ //both temporary lists have the same size
return true;
}
}
}else if( fst == null && snd == null ){
return true;
}
return false;
}
Advantages compared to some other solutions:
[1,2,3,3] and another array [1,2,2,3] most solutions here tell you they are the same when not considering the order. This solution avoids this by removing equal elements from the temporary lists;equals) and not reference equality (==);implement Comparable) for this solution to work.It is an alternative way to check equality of array lists which can contain null values:
List listA = Arrays.asList(null, "b", "c");
List listB = Arrays.asList("b", "c", null);
System.out.println(checkEquality(listA, listB)); // will return TRUE
private List<String> getSortedArrayList(List<String> arrayList)
{
String[] array = arrayList.toArray(new String[arrayList.size()]);
Arrays.sort(array, new Comparator<String>()
{
@Override
public int compare(String o1, String o2)
{
if (o1 == null && o2 == null)
{
return 0;
}
if (o1 == null)
{
return 1;
}
if (o2 == null)
{
return -1;
}
return o1.compareTo(o2);
}
});
return new ArrayList(Arrays.asList(array));
}
private Boolean checkEquality(List<String> listA, List<String> listB)
{
listA = getSortedArrayList(listA);
listB = getSortedArrayList(listB);
String[] arrayA = listA.toArray(new String[listA.size()]);
String[] arrayB = listB.toArray(new String[listB.size()]);
return Arrays.deepEquals(arrayA, arrayB);
}
This is based on @cHao solution. I included several fixes and performance improvements. This runs roughly twice as fast the equals-ordered-copy solution. Works for any collection type. Empty collections and null are regarded as equal. Use to your advantage ;)
/**
* Returns if both {@link Collection Collections} contains the same elements, in the same quantities, regardless of order and collection type.
* <p>
* Empty collections and {@code null} are regarded as equal.
*/
public static <T> boolean haveSameElements(Collection<T> col1, Collection<T> col2) {
if (col1 == col2)
return true;
// If either list is null, return whether the other is empty
if (col1 == null)
return col2.isEmpty();
if (col2 == null)
return col1.isEmpty();
// If lengths are not equal, they can't possibly match
if (col1.size() != col2.size())
return false;
// Helper class, so we don't have to do a whole lot of autoboxing
class Count
{
// Initialize as 1, as we would increment it anyway
public int count = 1;
}
final Map<T, Count> counts = new HashMap<>();
// Count the items in col1
for (final T item : col1) {
final Count count = counts.get(item);
if (count != null)
count.count++;
else
// If the map doesn't contain the item, put a new count
counts.put(item, new Count());
}
// Subtract the count of items in col2
for (final T item : col2) {
final Count count = counts.get(item);
// If the map doesn't contain the item, or the count is already reduced to 0, the lists are unequal
if (count == null || count.count == 0)
return false;
count.count--;
}
// At this point, both collections are equal.
// Both have the same length, and for any counter to be unequal to zero, there would have to be an element in col2 which is not in col1, but this is checked in the second loop, as @holger pointed out.
return true;
}
I'd say these answers miss a trick.
Bloch, in his essential, wonderful, concise Effective Java, says, in item 47, title "Know and use the libraries", "To summarize, don't reinvent the wheel". And he gives several very clear reasons why not.
There are a few answers here which suggest methods from CollectionUtils in the Apache Commons Collections library but none has spotted the most beautiful, elegant way of answering this question:
Collection<Object> culprits = CollectionUtils.disjunction( list1, list2 );
if( ! culprits.isEmpty() ){
// ... do something with the culprits, i.e. elements which are not common
}
Culprits: i.e. the elements which are not common to both Lists. Determining which culprits belong to list1 and which to list2 is relatively straightforward using CollectionUtils.intersection( list1, culprits ) and CollectionUtils.intersection( list2, culprits ).
However it tends to fall apart in cases like { "a", "a", "b" } disjunction with { "a", "b", "b" } ... except this is not a failing of the software, but inherent to the nature of the subtleties/ambiguities of the desired task.
You can always examine the source code (l. 287) for a task like this, as produced by the Apache engineers. One benefit of using their code is that it will have been thoroughly tried and tested, with many edge cases and gotchas anticipated and dealt with. You can copy and tweak this code to your heart's content if need be.
NB I was at first disappointed that none of the CollectionUtils methods provides an overloaded version enabling you to impose your own Comparator (so you can redefine equals to suit your purposes).
But from collections4 4.0 there is a new class, Equator which "determines equality between objects of type T". On examination of the source code of collections4 CollectionUtils.java they seem to be using this with some methods, but as far as I can make out this is not applicable to the methods at the top of the file, using the CardinalityHelper class... which include disjunction and intersection.
I surmise that the Apache people haven't got around to this yet because it is non-trivial: you would have to create something like an "AbstractEquatingCollection" class, which instead of using its elements' inherent equals and hashCode methods would instead have to use those of Equator for all the basic methods, such as add, contains, etc. NB in fact when you look at the source code, AbstractCollection does not implement add, nor do its abstract subclasses such as AbstractSet... you have to wait till the concrete classes such as HashSet and ArrayList before add is implemented. Quite a headache.
In the mean time watch this space, I suppose. The obvious interim solution would be to wrap all your elements in a bespoke wrapper class which uses equals and hashCode to implement the kind of equality you want... then manipulate Collections of these wrapper objects.
One-line method :)
Collection's items NOT implement the interface Comparable<? super T>
static boolean isEqualCollection(Collection<?> a, Collection<?> b) {
return a == b || (a != null && b != null && a.size() == b.size()
&& a.stream().collect(Collectors.toMap(Function.identity(), s -> 1L, Long::sum)).equals(b.stream().collect(Collectors.toMap(Function.identity(), s -> 1L, Long::sum))));
}
Collection's items implement the interface Comparable<? super T>
static <T extends Comparable<? super T>> boolean isEqualCollection2(Collection<T> a, Collection<T> b) {
return a == b || (a != null && b != null && a.size() == b.size() && a.stream().sorted().collect(Collectors.toList()).equals(b.stream().sorted().collect(Collectors.toList())));
}
support Android5 & Android6 via https://github.com/retrostreams/android-retrostreams
static boolean isEqualCollection(Collection<?> a, Collection<?> b) {
return a == b || (a != null && b != null && a.size() == b.size()
&& StreamSupport.stream(a).collect(Collectors.toMap(Function.identity(), s->1L, Longs::sum)).equals(StreamSupport.stream(b).collect(Collectors.toMap(Function.identity(), s->1L, Longs::sum))));
}
////Test case
boolean isEquals1 = isEqualCollection(null, null); //true
boolean isEquals2 = isEqualCollection(null, Arrays.asList("1", "2")); //false
boolean isEquals3 = isEqualCollection(Arrays.asList("1", "2"), null); //false
boolean isEquals4 = isEqualCollection(Arrays.asList("1", "2", "2"), Arrays.asList("1", "1", "2")); //false
boolean isEquals5 = isEqualCollection(Arrays.asList("1", "2"), Arrays.asList("2", "1")); //true
boolean isEquals6 = isEqualCollection(Arrays.asList("1", 2.0), Arrays.asList(2.0, "1")); //true
boolean isEquals7 = isEqualCollection(Arrays.asList("1", 2.0, 100L), Arrays.asList(2.0, 100L, "1")); //true
boolean isEquals8 = isEqualCollection(Arrays.asList("1", null, 2.0, 100L), Arrays.asList(2.0, null, 100L, "1")); //true
If you don't hope to sort the collections and you need the result that ["A" "B" "C"] is not equals to ["B" "B" "A" "C"],
l1.containsAll(l2)&&l2.containsAll(l1)
is not enough, you propably need to check the size too :
List<String> l1 =Arrays.asList("A","A","B","C");
List<String> l2 =Arrays.asList("A","B","C");
List<String> l3 =Arrays.asList("A","B","C");
System.out.println(l1.containsAll(l2)&&l2.containsAll(l1));//cautions, this will be true
System.out.println(isListEqualsWithoutOrder(l1,l2));//false as expected
System.out.println(l3.containsAll(l2)&&l2.containsAll(l3));//true as expected
System.out.println(isListEqualsWithoutOrder(l2,l3));//true as expected
public static boolean isListEqualsWithoutOrder(List<String> l1, List<String> l2) {
return l1.size()==l2.size() && l1.containsAll(l2)&&l2.containsAll(l1);
}
If the cardinality of items doesn't matter (meaning: repeated elements are considered as one), then there is a way to do this without having to sort:
boolean result = new HashSet<>(listA).equals(new HashSet<>(listB));
This will create a Set out of each List, and then use HashSet's equals method which (of course) disregards ordering.
If cardinality matters, then you must confine yourself to facilities provided by List; @jschoen's answer would be more fitting in that case.
My solution for this. It is not so cool, but works well.
public static boolean isEqualCollection(List<?> a, List<?> b) {
if (a == null || b == null) {
throw new NullPointerException("The list a and b must be not null.");
}
if (a.size() != b.size()) {
return false;
}
List<?> bCopy = new ArrayList<Object>(b);
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < bCopy.size(); j++) {
if (a.get(i).equals(bCopy.get(j))) {
bCopy.remove(j);
break;
}
}
}
return bCopy.isEmpty();
}
Apache Commons Collections to the rescue once again:
List<String> listA = Arrays.asList("a", "b", "b", "c");
List<String> listB = Arrays.asList("b", "c", "a", "b");
System.out.println(CollectionUtils.isEqualCollection(listA, listB)); // true
List<String> listC = Arrays.asList("a", "b", "c");
List<String> listD = Arrays.asList("a", "b", "c", "c");
System.out.println(CollectionUtils.isEqualCollection(listC, listD)); // false
org.apache.commons.collections4.CollectionUtils
public static boolean isEqualCollection(java.util.Collection a, java.util.Collection b)Returns
trueiff the givenCollections contain exactly the same elements with exactly the same cardinalities.That is, iff the cardinality of e in a is equal to the cardinality of e in b, for each element e in a or b.
Parameters:
a- the first collection, must not benullb- the second collection, must not benullReturns:
trueiff the collections contain the same elements with the same cardinalities.
// helper class, so we don't have to do a whole lot of autoboxing
private static class Count {
public int count = 0;
}
public boolean haveSameElements(final List<String> list1, final List<String> list2) {
// (list1, list1) is always true
if (list1 == list2) return true;
// If either list is null, or the lengths are not equal, they can't possibly match
if (list1 == null || list2 == null || list1.size() != list2.size())
return false;
// (switch the two checks above if (null, null) should return false)
Map<String, Count> counts = new HashMap<>();
// Count the items in list1
for (String item : list1) {
if (!counts.containsKey(item)) counts.put(item, new Count());
counts.get(item).count += 1;
}
// Subtract the count of items in list2
for (String item : list2) {
// If the map doesn't contain the item here, then this item wasn't in list1
if (!counts.containsKey(item)) return false;
counts.get(item).count -= 1;
}
// If any count is nonzero at this point, then the two lists don't match
for (Map.Entry<String, Count> entry : counts.entrySet()) {
if (entry.getValue().count != 0) return false;
}
return true;
}
Think how you would do this yourself, absent a computer or programming language. I give you two lists of elements, and you have to tell me if they contain the same elements. How would you do it?
One approach, as mentioned above, is to sort the lists and then go element-by-element to see if they're equal (which is what List.equals does). This means either you're allowed to modify the lists or you're allowed to copy them -- and without knowing the assignment, I can't know if either/both of those are allowed.
Another approach would be to go through each list, counting how many times each element appears. If both lists have the same counts at the end, they have the same elements. The code for that would be to translate each list to a map of elem -> (# of times the elem appears in the list) and then call equals on the two maps. If the maps are HashMap, each of those translations is an O(N) operation, as is the comparison. That's going to give you a pretty efficient algorithm in terms of time, at the cost of some extra memory.
Probably the easiest way for any list would be:
listA.containsAll(listB) && listB.containsAll(listA)
Solution which leverages CollectionUtils subtract method:
import static org.apache.commons.collections15.CollectionUtils.subtract;
public class CollectionUtils {
static public <T> boolean equals(Collection<? extends T> a, Collection<? extends T> b) {
if (a == null && b == null)
return true;
if (a == null || b == null || a.size() != b.size())
return false;
return subtract(a, b).size() == 0 && subtract(a, b).size() == 0;
}
}
Converting the lists to Guava's Multiset works very well. They are compared regardless of their order and duplicate elements are taken into account as well.
static <T> boolean equalsIgnoreOrder(List<T> a, List<T> b) {
return ImmutableMultiset.copyOf(a).equals(ImmutableMultiset.copyOf(b));
}
assert equalsIgnoreOrder(ImmutableList.of(3, 1, 2), ImmutableList.of(2, 1, 3));
assert !equalsIgnoreOrder(ImmutableList.of(1), ImmutableList.of(1, 1));
If you care about order, then just use the equals method:
list1.equals(list2)
If you don't care order then use this
Collections.sort(list1);
Collections.sort(list2);
list1.equals(list2)
Best of both worlds [@DiddiZ, @Chalkos]: this one mainly builds upon @Chalkos method, but fixes a bug (ifst.next()), and improves initial checks (taken from @DiddiZ) as well as removes the need to copy the first collection (just removes items from a copy of the second collection).
Not requiring a hashing function or sorting, and enabling an early exist on un-equality, this is the most efficient implementation yet. That is unless you have a collection length in the thousands or more, and a very simple hashing function.
public static <T> boolean isCollectionMatch(Collection<T> one, Collection<T> two) {
if (one == two)
return true;
// If either list is null, return whether the other is empty
if (one == null)
return two.isEmpty();
if (two == null)
return one.isEmpty();
// If lengths are not equal, they can't possibly match
if (one.size() != two.size())
return false;
// copy the second list, so it can be modified
final List<T> ctwo = new ArrayList<>(two);
for (T itm : one) {
Iterator<T> it = ctwo.iterator();
boolean gotEq = false;
while (it.hasNext()) {
if (itm.equals(it.next())) {
it.remove();
gotEq = true;
break;
}
}
if (!gotEq) return false;
}
// All elements in one were found in two, and they're the same size.
return true;
}
Source: Stackoverflow.com