5

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;
    }
Improve this question

2 Answers 2

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Looking great!!!!!!! can you somehow remove this single loop if possible
@Mohtisham, do you want to rewrite outer for loop to Stream API as well? Well, technically it's "reduceLeft" or "foldLeft" operation. Standard Stream API has no such thing, but if you don't care about parallelism, you can use simple reduce providing bogus combiner. However this will not make code better. Here's the implementation using my free StreamEx library (which actually has foldLeft). Without StreamEx it would look even worse.
I am totally lost in order to understand whats going on, can you commentate whats your code doing for both cases. I know it is a big ask and weird also, but I am feeling totally helpless to conceive your art.
Leave the for loop I just want fully grab the idea of your code in order to use in future scenarios
@Mohtisham added some comments
|
1

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.

Improve this answer

5 Comments

This is failing for 1 test case. Giving only 1 list with element 3.
@Mohtisham It works fine with me. Did you feed it a List<List<Integer>>? Try System.out.println(combineList(Collections.singletonList(Collections.singletonList(3))));, it prints out "[[3]]".
but it should print [[0,1,2][3]]
@Mohtisham Then I may have misunderstood your question. From what I understand, you want an algorithm that can merge lists that share a common element? Then, where does [0, 1, 2] come from? Does your function add new elements?
Though it is working with unnecessary loop and deleting logic but I want something like, which I updated in mine question, though Tagir answer is the best one and well above what I had in mine mind

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.