LinkedList of LinkedList with recursion - loop issue

Question

I have a List of Lists structure and a recursive function called tree. In the following code it NEVER reaches the current == null statement so it will run forever.

If I cannot use null, what is the solution?

private void tree(LinkedList<LinkedList<String>> partitions, LinkedList<String> part)
{
    LinkedList<String> current = findBiggerPartitionContained(partitions, part);
    if (current == null) {
        return;
    }
    tree(partitions, current);
}

private LinkedList<String> findBiggerPartitionContained(LinkedList<LinkedList<String>> partitions, LinkedList<String> part)
{
    LinkedList<String> max = new LinkedList<>();

    boolean flag = false;
    for (LinkedList<String> item : partitions) {
        if (item.size() > max.size() && part.containsAll(max)) {
            max = item;
            flag = true;
        }
    }

    if (!flag)
        return null;
    flag = false;
    return max;
}

Judging by your code, it should be current.isEmpty() instead of current==null — Zircon
– Zircon, Commented Oct 18, 2016 at 20:28
I am confused, should you change you condition into "part.containsAll(item))" instead? — sramij
– sramij, Commented Oct 18, 2016 at 21:48

Community · Accepted Answer · 2017-05-23 10:27:30Z

Most of the time flag will be true because your condition tests item.size() > max.size(), and max is initialized with an empty list. When max is empty, the expression part.containsAll(max) will be true as well, which leads to unexpected results.

In order to fix this, you can use this in findBiggerPartitionContained:

if (item.size() > max.size() && item.containsAll(part)) {
    max = item;
    flag = true;
}

And this in tree:

if (current.equals(part)) {
    return;
} else {
    tree(partitions, current);
}

If I have understood correctly, you're looking for the biggest list in partitions which contains part. Maybe the following is less error prone and more readable:

List<String> result = partitions.stream().filter(list -> list.containsAll(part))
                                         .max(Comparator.comparingInt(List::size))
                                         .orElse(null);

You can test it with this MCVE:

List<String> p0 = new LinkedList<>(Arrays.asList("a", "b", "c"));
List<String> p1 = new LinkedList<>(Arrays.asList("a", "b"));
List<String> p2 = new LinkedList<>(Arrays.asList("a", "b", "c", "d"));
List<String> p3 = new LinkedList<>(Arrays.asList("a", "b", "e", "d"));
List<List<String>> partitions = Arrays.asList(p0, p1, p2, p3);

List<String> part = new LinkedList<>(Arrays.asList("a", "b", "e"));

List<String> result = partitions.stream().filter(list -> list.containsAll(part))
                                         .max(Comparator.comparingInt(List::size))
                                         .orElse(null);

System.out.println(result);

Bear in mind that this may returns null to handle absent Optionals.

Collectives™ on Stack Overflow

LinkedList of LinkedList with recursion - loop issue

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related