Какое элегантное решение существует для этого шаблона? Многоуровневый поиск

Question

Предположим, что у нас есть несколько массивов целых чисел. Вы можете рассматривать каждый массив как уровень. Мы пытаемся найти последовательность элементов, ровно один элемент из каждого массива, и переходим к следующему массиву с одним и тем же предикатом. Например, мы имеем v1, v2, v3 как массивы:

v1 | v2 | v3 
----------------- 
1 | 4 | 16 
2 | 5 | 81 
3 | 16 | 100 
4 | 64 | 121 

Я мог бы сказать, что предикат: next_element == previous_element^2
Действительная последовательность из приведенного выше примера: 2 -> 4 -> 16
На самом деле, в этом примере нет другого действительная последовательность. Я мог бы написать три петли для перебора приведенного примера, , но что, если количество массивов является переменным, но с уверенностью, конечно, как бы вы решили эту проблему?

Подсказки или ссылки на дизайн-паттерны очень ценятся. Я сделаю это на C++, но мне просто нужна эта идея.

Спасибо,

Answer 1

Если вы заказываете ваши массивы заранее, поиск может быть сделано намного быстрее. Вы можете начать с вашего меньшего массива, затем двоично-искать ожидаемые числа на каждом из них. Это было бы O (п к logM), п быть размером наименьшего массива, где К число массивов, где М размер большего массива

Это может быть сделано даже быстрее, если вы используете HashMaps вместо массивов. Это позволит вам искать в O (n * k).

Если использование обратных функций (для поиска в ранних массивах) не является опцией, то вы должны начать с первого массива и n = размер первого массива.

Для простоты, я начну с первого массива

//note the 1-based arrays 
for (i : 1 until allArrays[1].size()) { 
    baseNumber = allArrays[1][i]; 
    for (j: 2 until allArrays.size()) { 
    expectedNumber = function(baseNumber); 
    if (!find(expectedNumber, allArrays[j])) 
     break; 
    baseNumber = expectedNumber; 
    } 
} 

Вы можете, вероятно, сделать некоторые пустые чеки и добавить некоторые булевы там, чтобы знать, если последовательность существует или не

Answer 2

Вы могли бы генерировать отдельный индекс, который отображает индекс из одного массива в индекс другого. Из индекса вы можете быстро увидеть, существует ли решение или нет.

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

Answer 3

Я бы сохранил все векторы как heaps, так что я могу иметь O(log n) сложность при поиске элемента. Так в общей сложности k векторов вы получите сложность как O(k * log n)

Answer 4

(Шаблоны проектирования применяются к классу и дизайну API, чтобы улучшить качество кода, но они не для решения вычислительных задач.)

В зависимости от случаи:

1. Если массивы поступают в случайном порядке, и у вас есть ограниченное пространство, то грубая сила является единственным решением. O (N ^k) время (k = 3), O (1) пробел.
2. Если предикат не является обратимым (например,SHA1(next_elem) xor SHA1(prev_elem) == 0x1234), то грубая сила также является единственным решением.
3. Если вы можете потратить пространство, то создайте хэш-множества для v2 и v3, чтобы вы могли быстро найти следующий элемент, который удовлетворяет предикату. O (N + b ^k) время, O (kN) пространство. (b = максимальное число next_elem, которое удовлетворяет предикату с учетом prev_elem)
4. Если массивы отсортированы и ограничены, вы можете также использовать двоичный поиск вместо хеш-таблицы, чтобы избежать использования пространства. O (N (log N) ^k-1 + b ^k) время, O (1) место.

(Все подсчета пространства не учитывает стек использование из-за рекурсии.)

Общий способ, который потребляет до O (Nb ^к) пространство, чтобы построить решение, последовательная фильтрация, например

solutions = [[1], [2], ... [N]] 

filterSolution (Predicate, curSols, nextElems) { 
    nextSols = [] 
    for each curSol in curSols: 
     find elem in nextElems that satisfy the Predicate 
     append elem into a copy of curSol, then push into nextSols 
    return nextSols 
} 

for each levels: 
    solutions = filterSolution(Predicate, solutions, all elems in this level) 
return solutions 

Answer 5

Если предикаты сохранить порядок в массивах (например, с помощью, например, если значения всех гарантируется неотрицательным), вы могли бы адаптировать алгоритм слияния. Рассмотрим ключ для каждого массива как конечную величину (что вы получаете после применения предиката столько раз, сколько необходимо для всех массивов).

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

В принципе, проверьте, соответствует ли следующее конечное значение для всех массивов. Если нет, перейдите к самому низкому (только в одном массиве) и повторите. Если вы получите все три равных, то это (возможное) решение - перейдите все три перед поиском следующего.

«Возможное» решение, потому что вам может потребоваться проверка - если функция предиката может отображать более одного входного значения в одно и то же значение вывода, у вас может быть случай, когда значение найдено в некоторых массивах (но не в первый или последний) является неправильным.

РЕДАКТИРОВАТЬ - могут возникнуть большие проблемы, когда предикат не отображает каждый вход в уникальный выход - в настоящий момент не может думать. В принципе, подход слияния может работать хорошо, но только для определенных видов предикатной функции.