Подсчитать все списки соседних узлов, хранящихся в массиве

Question

Есть много наивных подходов к этой проблеме, но я ищу хорошее решение. Вот проблема (будет реализована в Java):

У вас есть функция foo (int a, int b), которая возвращает true, если «a» «соседствует» с «b», и false, если «a» не смежна с «b». У вас есть такой массив [1,4,5,9,3,2,6,15,89,11,24], но в действительности он имеет очень большую длину, например 120, и будет повторяться снова и снова (это фитнес-функция генетического алгоритма), поэтому эффективность важна.

Мне нужна функция, которая возвращает длину каждого возможного «списка» смежностей в массиве, но не включает «списки», которые просто являются подмножествами большего списка.

Например, если 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, тогда есть «списки» (1,4,5) и (9,3,2,6), поэтому длина 3 и 4. Я надеваю не хочу, чтобы он возвращал (3,2,6), потому что это просто подмножество 9,3,2,6.

Спасибо.

EDIT

Извините, я только что понял, что не объяснил всю проблему, а оставшаяся часть - это то, что так сложно. Позволяет перезагрузить. Забудьте первый пост. Это смущает нас.

Допустим, есть функция foo (массив int []), которая возвращает истину, если массив является «хорошим» массивом, и ложь, если массив является «плохим» массивом. То, что делает это хорошим или плохим, здесь не имеет значения.

Учитывая полный массив [1,6,8,9,5,11,45,16,9], допустим, что подмассив [1,6,8] является «хорошим» массивом и [9,5, 11,45] - это «хороший» массив. Кроме того, [5,11,45,16,9] является «хорошим» массивом, а также самым длинным «хорошим» массивом. Обратите внимание, что хотя [9,5,11,45] является «хорошим» массивом, а [5,11,45,16,9] является «хорошим» массивом, [9,5,11,45,16,9 ] - «плохой» массив.

Мы хотим, чтобы счетчики длины всех "хороших" массивов, но не подмассивы "хороших" массивов. Кроме того, как описано выше, «хороший» массив может начинаться в середине другого «хорошего» массива, но комбинация этих двух может быть «плохим» массивом.

Answer 1

Я думаю, что O(n) алгоритм делает то, что вы хотите. Я сомневаюсь, что вы можете сделать это быстрее, так как вам придется анализировать каждый элемент.

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

Это работает, потому что если определенное число разрывает цепочку смежности, то ни одно из чисел перед числом, которое разорвало цепочку, не может быть частью более длинной цепочки, так что вы можете продолжить с этого момента.

Работа над этим примером:

Например, если 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, тогда есть «списки» (1,4,5) и (9,3,2,6), поэтому длина 3 и 4. Я надеваю не хочу, чтобы он возвращал (3,2,6), потому что это просто подмножество 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

конец массива, просто выведите количество, так что print 5. Я предполагаю, что ваш пример неверен, потому что (9, 3, 2, 6) является подмножеством (9, 3, 2, 6, 15) ...

Answer 2

Это, я думаю, в классе проблем стиля с самой длинной подстрокой, которые могут быть решены за один проход (в O(n)), при условии, что у вас есть свойство, что если подмассив от A до B равен " хорошо ", то любой меньший подмассив тоже хорош.

Алгоритм выглядит так:

• Начните с подмассива, состоящего из первого элемента (или пары, или любой другой наименьшей возможной единицы).
• Маршируйте подмассив вперед (т. Е. Сдвигайте начало и конец подмассива), пока не получите ответ «хорошо».
• Продвигайте конец подмассива, пока не получите ответ «плохо». Подмассив незадолго до того, как вы получили «плохой», был самым длинным хорошим подмассивом в этом месте - сосчитайте его (или сохраните, или все, что вы хотите с ним сделать).
• Теперь продвигайте начало подмассива, пока не получите ответ «хорошо»; если вы дойдете до конца подмассива, сдвиньте оба вперед. Затем повторите предыдущий шаг.
• Когда конец вашего подмассива достигает конца вашего полного массива, все готово.