Это может быть легко преобразовано в проблему другого типа, которая может быть решена более эффективно. Все, что нужно, - это преобразовать массивы в перестановки, то есть изменить значения на их идентификаторы. Итак, ваши массивы:
L1 = [2,3,4,5]
L2 = [2,5,4,3]
станет
P1 = [0,1,2,3]
P2 = [0,3,2,1]
с присвоением 2->0, 3->1, 4->2, 5->3. Это может быть сделано только если нет повторяющихся предметов, хотя. Если есть, то это становится труднее решить.
Преобразование перестановки из одной в другую может быть преобразовано в аналогичную проблему ( Число перестановок в перестановке ) путем инвертирования целевой перестановки в O (n), составления перестановок в O (n) и затем найти число перестановок оттуда к тождественной перестановке в O (m).
Дано:
int P1[] = {0, 1, 2, 3}; // 2345
int P2[] = {0, 3, 2, 1}; // 2543
// we can follow a simple algebraic modification
// (see http://en.wikipedia.org/wiki/Permutation#Product_and_inverse):
// P1 * P = P2 | premultiply P1^-1 *
// P1^-1 * P1 * P = P1^-1 * P2
// I * P = P1^-1 * P2
// P = P1^-1 * P2
// where P is a permutation that makes P1 into P2.
// also, the number of steps from P to identity equals
// the number of steps from P1 to P2.
int P1_inv[4];
for(int i = 0; i < 4; ++ i)
P1_inv[P1[i]] = i;
// invert the first permutation in O(n)
int P[4];
for(int i = 0; i < 4; ++ i)
P[i] = P2[P1_inv[i]];
// chain the permutations in O(n)
int num_steps = NumSteps(P, 4); // will return 2
// now we just need to count the steps in O(num_steps)
Для подсчета шагов может быть разработан простой алгоритм, такой как:
int NumSteps(int *P, int n)
{
int count = 0;
for(int i = 0; i < n; ++ i) {
for(; P[i] != i; ++ count) // could be permuted multiple times
swap(P[P[i]], P[i]); // look where the number at hand should be
}
// count number of permutations
return count;
}
Это всегда меняет предмет на место, где он должен находиться в перестановке идентификаторов, поэтому на каждом шаге он отменяет и учитывает один обмен. Теперь, при условии, что количество возвращаемых свопов действительно минимально, время выполнения алгоритма ограничено им и гарантированно завершится (вместо того, чтобы застрять в бесконечном цикле). Он будет выполняться в O(m) swaps или O(m + n) loop циклах, где m - это количество свопов (возвращается count), а n - количество элементов в последовательности (4). Обратите внимание, что m < n всегда верно. Следовательно, это должно быть лучше, чем O(n log n) решения, так как верхняя граница здесь равна O(n - 1) свопов или O(n + n - 1) итераций цикла, что практически равно O(n) (постоянный коэффициент 2 в последнем случае опущен).
Алгоритм будет работать только для допустимых перестановок, он будет бесконечно циклически повторяться для последовательностей с дублирующимися значениями и будет осуществлять доступ к массиву вне пределов (и сбой) для последовательностей со значениями, отличными от [0, n). Полный тестовый пример можно найти здесь (сборка с Visual Studio 2008, сам алгоритм должен быть достаточно переносимым). Он генерирует все возможные перестановки длины от 1 до 32 и проверяет решения, сгенерированные с помощью поиска в ширину (BFS), кажется, работает для всех перестановок длины от 1 до 12, затем он становится довольно медленным, но я предполагаю, что он просто продолжит работать .