Count all lists of adjacent nodes stored in an array.

Question

There are many naive approaches to this problem, but I'm looking for a good solution. Here is the problem (will be implemented in Java):

You have a function foo(int a, int b) that returns true if 'a' is "adjacent" to 'b' and false if 'a' is not adjacent to 'b'. You have an array such as this [1,4,5,9,3,2,6,15,89,11,24], but in reality has a very long length, like 120, and will be repeated over and over (its a genetic algorithm fitness function) which is why efficiency is important.

I want a function that returns the length of each possible 'list' of adjacencies in the array, but not including the 'lists' which simply subsets of a larger list.

For example, if foo(1,4) -> true, foo(4,5) -> true, foo(5,9)-> false, foo(9,3) & foo(3,2) & foo(2,6), foo(6,15) -> true, then there are 'lists' (1,4,5) and (9,3,2,6), so length 3 and 4. I don't want it to return (3,2,6), though, because this is simply a subset of 9,3,2,6.

Thanks.

Answer 1

I think this O(n) algorithm does what you want. I doubt you can do this faster since you have to analyse each element.

count = 1;
for each index i from 1 to N
    if ( foo(array[i-1], array[i]) == true )
        ++count;
    else
        print count;
        count = 1;

This works because if a certain number breaks the adjacency chain, then none of the numbers before the number that broke the chain can be part of a longer chain, so you might as well continue from that point on.

Working this on your example:

For example, if foo(1,4) -> true, foo(4,5) -> true, foo(5,9)-> false, foo(9,3) & foo(3,2) & foo(2,6), foo(6,15) -> true, then there are 'lists' (1,4,5) and (9,3,2,6), so length 3 and 4. I don't want it to return (3,2,6), though, because this is simply a subset of 9,3,2,6

foo(1, 4) -> true -> count = 2
foo(1, 5) -> true -> count = 3
foo(5, 9) -> false -> print 3, count = 1
foo(9, 3) -> true -> count = 2
foo(3, 2) -> true -> count = 3
foo(2, 6) -> true -> count = 4
foo(6, 15) -> true -> count = 5

end of array, just print count, so print 5. I'm guessing your example is wrong, because (9, 3, 2, 6) is a subset of (9, 3, 2, 6, 15)...

Answer 2

Sorry I just realized I didn't explain the whole problem, and the remaining portion is what is so difficult. Lets restart. Forget the first post. That will confuse us.

Lets say there is a function foo(int[] array) that returns true if the array is a "good" array and false if the array is a "bad" array. What makes it good or bad does not matter here.

Given the full array [1,6,8,9,5,11,45,16,9], lets say that subarray [1,6,8] is a "good" array and [9,5,11,45] is a "good" array. Furthermore [5,11,45,16,9] is a "good" array, and also the longest "good" subarray. Notice that while [9,5,11,45] is a "good" array, and [5,11,45,16,9] is a "good" array, [9,5,11,45,16,9] is a "bad" array.

We wants the length counts of all "good" arrays, but not subarrays of "good" arrays. Furthermore, as described above, a "good" array might begin in the middle of another "good" array, but the combination of the two might be a "bad" array.

Answer 3

This is, I think, in the class of longest-substring style problems which can be solved in a single pass (in O(n)), as long as you have the property that if the subarray from A to B is "good", then any smaller subarray is also good.

The algorithm goes like this:

• Start with a subarray consisting of the first element (or pair, or whatever the shortest possible unit is).
• March the subarray forward (i.e. advance both start and end of the subarray) until you get the answer "good".
• Advance the end of the subarray until you get the answer "bad". The subarray just before you got "bad" was the longest good subarray at that location--count it (or save it, or whatever you wish to do with it).
• Now advance the start of the subarray until you get the answer "good"; if you catch up to the end of the subarray, slide both forwards. Then repeat the previous step.
• When the end of your subarray hits the end of your full array, you're done.