Count all lists of adjacent nodes stored in an array.
- by Ben Brodie
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.
