Java: See if ArrayList contains ArrayList with duplicate values

Question

I'm currently trying to create a method that determine if an ArrayList(a2) contains an ArrayList(a1), given that both lists contain duplicate values (containsAll wouldn't work as if an ArrayList contains duplicate values, then it would return true regardless of the quantity of the values)

This is what I have: (I believe it would work however I cannot use .remove within the for loop)

public boolean isSubset(ArrayList<Integer> a1, ArrayList<Integer> a2) {
    Integer a1Size= a1.size();
    for (Integer integer2:a2){
        for (Integer integer1: a1){
            if (integer1==integer2){
                a1.remove(integer1);
                a2.remove(integer2);
                if (a1Size==0){
                    return true;
                }
            }
        }
    }
    return false;
}

Thanks for the help.

Answer 1

Updated

I think the clearest statement of your question is in one of your comments:

Yes, the example " Example: [dog,cat,cat,bird] is a match for containing [cat,dog] is false but containing [cat,cat,dog] is true?" is exactly what I am trying to achieve.

So really, you are not looking for a "subset", because these are not sets. They can contain duplicate elements. What you are really saying is you want to see whether a1 contains all the elements of a2, in the same amounts.

One way to get to that is to count all the elements in both lists. We can get such a count using this method:

private Map<Integer, Integer> getCounter (List<Integer> list) {
    Map<Integer, Integer> counter = new HashMap<>();
    for (Integer item : list) {
        counter.put (item, counter.containsKey(item) ? counter.get(item) + 1 : 1);
    }
    return counter;
}

We'll rename your method to be called containsAllWithCounts(), and it will use getCounter() as a helper. Your method will also accept List objects as its parameters, rather than ArrayList objects: it's a good practice to specify parameters as interfaces rather than implementations, so you are not tied to using ArrayList types.

With that in mind, we simply scan the counts of the items in a2 and see that they are the same in a1:

  public boolean containsAllWithCounts(List<Integer> a1, List<Integer> a2) {
        Map<Integer,Integer> counterA1 = getCounter(a1);
        Map<Integer,Integer> counterA2 = getCounter(a2);

        boolean containsAll = true;
        for (Map.Entry<Integer, Integer> entry : counterA2.entrySet ()) {
            Integer key = entry.getKey();
            Integer count = entry.getValue();
            containsAll &= counterA1.containsKey(key) && counterA1.get(key).equals(count);
            if (!containsAll) break;
        }

        return containsAll;
    }

If you like, I can rewrite this code to handle arbitrary types, not just Integer objects, using Java generics. Also, all the code can be shortened using Java 8 streams (which I originally used - see comments below). Just let me know in comments.

Answer 2

if you want remove elements from list you have 2 choices:

• iterate over copy
• use concurrent list implementation

see also:

http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#synchronizedList-java.util.List-

btw why you don't override contains method ??

here you use simple Object like "Integer" what about when you will be using List< SomeComplexClass > ??

example remove with iterator over copy:

    List<Integer> list1 = new ArrayList<Integer>();
    List<Integer> list2 = new ArrayList<Integer>();

    List<Integer> listCopy = new ArrayList<>(list1);
    Iterator<Integer> iterator1 = listCopy.iterator();
    while(iterator1.hasNext()) {
        Integer next1 = iterator1.next();
        Iterator<Integer> iterator2 = list2.iterator();
        while (iterator2.hasNext()) {
            Integer next2 = iterator2.next();
            if(next1.equals(next2)) list1.remove(next1);
        }
    }

see also this answer about iterator:

Concurrent Modification exception

also don't use == operator to compare objects :) instead use equal method

about use of removeAll() and other similarly methods:

keep in mind that many classes that implements list interface don't override all methods from list interface - so you can end up with unsupported operation exception - thus I prefer "low level" binary/linear/mixed search in this case.

and for comparison of complex classes objects you will need override equal and hashCode methods

f you want to remove the duplicate values, simply put the arraylist(s) into a HashSet. It will remove the duplicates based on equals() of your object. - Olga

In Java, HashMap works by using hashCode to locate a bucket. Each bucket is a list of items residing in that bucket. The items are scanned, using equals for comparison. When adding items, the HashMap is resized once a certain load percentage is reached.

So, sometimes it will have to compare against a few items, but generally it's much closer to O(1) than O(n).

in short - there is no need to use more resources (memory) and "harness" unnecessary classes - as hash map "get" method gets very expensive as count of item grows.

  hashCode -> put to bucket  [if many item in bucket] -> get  = linear scan 

  so  what counts in removing items ? 

complexity of equals and hasCode and used of proper algorithm to iterate

Answer 3

If you want to remove the duplicate values, simply put the arraylist(s) into a HashSet. It will remove the duplicates based on equals() of your object.

Answer 4

I know this is maybe amature-ish, but...

There is no need to remove the items from both lists, so, just take it from the one list

public boolean isSubset(ArrayList<Integer> a1, ArrayList<Integer> a2) {
    for(Integer a1Int : a1){
        for (int i = 0; i<a2.size();i++) {
            if (a2.get(i).equals(a1Int)) {
                a2.remove(i);
                break;
            }
        }
        if (a2.size()== 0) {

            return true;
        }
    }
    return false;
}