Using java8 Streams merge internal lists within a list

Question

I want to merge inner Lists using java8 streams for following like this:

When

List<List<Integer>> mainList =  new ArrayList<List<Integer>>();
        mainList.add(Arrays.asList(0,1));
        mainList.add(Arrays.asList(0,1,2));
        mainList.add(Arrays.asList(1,2));
        mainList.add(Arrays.asList(3));

should be merged into

  [[0,1,2],[3]];       

And When

List<List<Integer>> mainList =  new ArrayList<List<Integer>>();
        mainList.add(Arrays.asList(0,2));
        mainList.add(Arrays.asList(1,4));
        mainList.add(Arrays.asList(0,2,4));
        mainList.add(Arrays.asList(3,4));      
        mainList.add(Arrays.asList(1,3,4));

should be merged into

 [[0,1,2,3,4]];                

This is so far what I have done

static void mergeCollections(List<List<Integer>> collectionTomerge) {
    boolean isMerge = false;
    List<List<Integer>> mergeCollection = new ArrayList<List<Integer>>();

    for (List<Integer> listInner : collectionTomerge) {
        List<Integer> mergeAny = mergeCollection.stream().map(
                lc -> lc.stream().filter(listInner::contains)
        ).findFirst()
                .orElse(null)
                .collect(Collectors.toList());
    }
}

but I am getting this exception:

Exception in thread "main" java.lang.NullPointerException
at linqArraysOperations.LinqOperations.mergeCollections(LinqOperations.java:87)

Updated with mine version of answer

That's what I want to achieve but great answer of Tagir is without recursion

I change things a bit in Mikhaal answer to achieve this, by using logic from Tagir answer without flat map

public static <T> List<List<T>> combineList(List<List<T>> argList) {
       boolean isMerge = false;
       List<List<T>> result = new ArrayList<>();

       for (List<T> list : argList) {
                                List<List<T>> mergedFound =
                                        result.stream()
                                        .filter(mt->list.stream().anyMatch(mt::contains))
                                        .map(
                                              t ->  Stream.concat(t.stream(),list.stream()).distinct()
                                              .collect(Collectors.toList())
                                             )
                                       .collect(Collectors.toList());

                //if(mergedFound !=null && ( mergedFound.size() > 0 &&  mergedFound.stream().findFirst().get().size() > 0 )){
        if(mergedFound !=null &&  mergedFound.size() > 0 && ){
                   result = Stream.concat(result.stream().filter(t->list.stream().noneMatch(t::contains)),mergedFound.stream()).distinct().collect(Collectors.toList());
                   isMerge = true;
                }
                else
                    result.add(list);

       }
       if(isMerge && result.size() > 1)
          return  combineList(result);
        return result;
    }

Answer 1

Here's very simple, yet not very efficient solution:

static List<List<Integer>> mergeCollections(List<List<Integer>> input) {
    List<List<Integer>> result = Collections.emptyList();

    for (List<Integer> listInner : input) {
        List<Integer> merged = Stream.concat(
                // read current results and select only those which contain
                // numbers from current list
                result.stream()
                      .filter(list -> list.stream().anyMatch(listInner::contains))
                      // flatten them into single stream
                      .flatMap(List::stream),
                // concatenate current list, remove repeating numbers and collect
                listInner.stream()).distinct().collect(Collectors.toList());

        // Now we need to remove used lists from the result and add the newly created 
        // merged list
        result = Stream.concat(
                result.stream()
                      // filter out used lists
                      .filter(list -> list.stream().noneMatch(merged::contains)),
                Stream.of(merged)).collect(Collectors.toList());
    }
    return result;
}

The tricky part is that next listInner may merge several lists which were already added. For example, if we had partial result like [[1, 2], [4, 5], [7, 8]], and processing a new listInner which content is [2, 3, 5, 7], then partial result should become [[1, 2, 3, 4, 5, 7, 8]] (that is, all lists are merged together). So on every iteration we are looking for existing partial results which have common numbers with current listInner, flatten them, concatenating with current listInner and dumping into the new merged list. Next we filter out from the current result lists which were used in merged and adding merged there.

You can make the solution somewhat more efficient using partitioningBy collector to perform both filtering steps at once:

static List<List<Integer>> mergeCollections(List<List<Integer>> input) {
    List<List<Integer>> result = Collections.emptyList();

    for (List<Integer> listInner : input) {
        // partition current results by condition: whether they contain
        // numbers from listInner
        Map<Boolean, List<List<Integer>>> map = result.stream().collect(
                Collectors.partitioningBy(
                        list -> list.stream().anyMatch(listInner::contains)));

        // now map.get(true) contains lists which intersect with current
        //    and should be merged with current
        // and map.get(false) contains other lists which should be preserved 
        //    in result as is
        List<Integer> merged = Stream.concat(
                map.get(true).stream().flatMap(List::stream),
                listInner.stream()).distinct().collect(Collectors.toList());
        result = Stream.concat(map.get(false).stream(), Stream.of(merged))
                       .collect(Collectors.toList());
    }
    return result;
}

Here map.get(true) contains the lists which have elements from listInner and map.get(false) contains other lists which should be preserved from the previous result.

The order of elements is probably not what you would expect, but you could easily sort nested lists or use List<TreeSet<Integer>> as resulting data structure if you want.

Answer 2

For the exception you're getting, I would guess that the List<List<Integer>> that the mergeCollections is being passed contains null values, and that those throw NullPointerException on listInner::contains.

Second, if I understand your problem correctly, you want an algorithm that can merge lists that share a common element. I came up with this to solve your problem:

public class Combiner {

    public static void main(String[] args) {
        List<List<Integer>> mainList = new ArrayList<>();
        mainList.add(Arrays.asList(1, 2));
        mainList.add(Arrays.asList(4, 5));
        mainList.add(Arrays.asList(7, 8));
        mainList.add(Arrays.asList(6, 19));

        mainList.add(Arrays.asList(2, 3, 5, 7));

        System.out.println(combineList(new ArrayList<>(mainList)));
        List<List<Integer>> result = mergeCollections(new ArrayList<>(mainList));
        System.out.println(result);

    }

    public static <T> List<List<T>> combineList(List<List<T>> argList) {
        List<List<T>> result = new ArrayList<>();
        for (List<T> list : argList) {
            //Copy the given list
            List<T> addedList = new ArrayList<>(list);
            result.add(addedList);
            for (List<T> otherList : argList) {
                if (list.equals(otherList)) continue;
                //If at least one element is shared between the two lists
                if (list.stream().anyMatch(otherList::contains)) {
                    //Add all elements that are exclusive to the second list
                    addedList.addAll(otherList.stream().map(t -> addedList.contains(t) ? null : t)
                            .filter(t -> t != null).collect(Collectors.toList()));
                }
            }
        }
        List<List<T>> del = new ArrayList<>();
        for (int i = 0; i < result.size(); i++) {
            for (int j = i + 1; j < result.size(); j++) {
                List<T> list = result.get(j);
                if (listEqualsUnOrdered(list, result.get(i))) {
                    //Modified this
                    del.add(result.get(i));
                }
            }
            //Can't use listIterator here because of iterating starting at j + 1
            result.removeAll(del);
        }
        //Recursion
        if (!result.equals(argList)) {
            result = combineList(result);
        }
        return result;
    }

    private static <T> boolean listEqualsUnOrdered(List<T> list1, List<T> list2) {
        if (list1.size() != list2.size()) return false;
        List<T> testOne = new ArrayList<>(list1);
        testOne.removeAll(list2);
        boolean testOnePassed = (testOne.size() == 0);
        List<T> testTwo = new ArrayList<>(list2);
        testTwo.removeAll(list1);
        if (testTwo.size() == 0 && testOnePassed) return true;
        return false;
    }
}

The algorithm is fairly simple, it uses a simple recursion to run the algorithm until the output is "clean", i.e. until the lists have been completely merged. I haven't done any optimizing, but it does what it's supposed to do.

Note that this method will also merge your existing list.