Как можно выдержать сравнение, до какой степени два списка находятся в том же порядке?

Просто идея, но там какой-либо пробег в адаптации стандартного алгоритма сортировки для подсчета, количество операций подкачки должно было преобразовать list1 в list2?

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

править: думая об этом немного больше, сравнить функция была бы по существу определена самим целевым списком. Так, например, если список 2:

1 4 6 5 3

... затем сравнить функция должна привести к 1 <4 <6 <5 <3 (и равенство возврата, где записи равны).

Затем функция подкачки просто должна быть расширена для подсчета операций подкачки.

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

См.: http://en.wikipedia.org/wiki/Levenshtein_distance

Хотя я не думаю, что l-расстояние принимает во внимание вращение. Если Вы позволяете вращение как операцию затем:

1, 2, 3, 4

и

2, 3, 4, 1

Довольно подобны.

Существует алгоритм метода ветвей и границ, который должен работать на любой набор операторов, которые Вы любите. Это не может быть очень быстро. Псевдокод проходит примерно так:

bool bounded_recursive_compare_routine(int* a, int* b, int level, int bound){
    if (level > bound) return false;
    // if at end of a and b, return true
    // apply rule 0, like no-change
    if (*a == *b){
        bounded_recursive_compare_routine(a+1, b+1, level+0, bound);
        // if it returns true, return true;
    }
    // if can apply rule 1, like rotation, to b, try that and recur
    bounded_recursive_compare_routine(a+1, b+1, level+cost_of_rotation, bound);
    // if it returns true, return true;
    ...
    return false;
}

int get_minimum_cost(int* a, int* b){
    int bound;
    for (bound=0; ; bound++){
        if (bounded_recursive_compare_routine(a, b, 0, bound)) break;
    }
    return bound;
}

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

Добавленный: Это может быть расширено для нахождения ближайшей соответствующей строки сохраненной в trie. Я сделал это несколько лет назад в алгоритме исправления орфографических ошибок.

Я не уверен точно, какую формулу это использует под капотом, но difflib.SequenceMatcher.ratio() делает точно это:

ratio(self) method of difflib.SequenceMatcher instance:
    Return a measure of the sequences' similarity (float in [0,1]).

Пример кода:

from difflib import SequenceMatcher
sm = SequenceMatcher(None, '1234', '1324')
print sm.ratio()

>>> 0.75

Другой подход, который основан на определенной математике, должен считать количество инверсий для преобразования одного из массивов в другой. Инверсия является обменом двумя соседними элементами массива. В рубине это сделано как это:

# extend class array by new method
class Array
  def dist(other)
    raise 'can calculate distance only to array with same length' if length != other.length
    # initialize count of inversions to 0
    count = 0
    # loop over all pairs of indices i, j with i<j
    length.times do |i|
      (i+1).upto(length) do |j|
        # increase count if i-th and j-th element have different order
        count += 1 if (self[i] <=> self[j]) != (other[i] <=> other[j])
      end
    end
    return count
  end
end
l1 = [1, 2, 3, 4]
l2 = [1, 3, 2, 4]
# try an example (prints 1)
puts l1.dist(l2)

Расстояние между двумя массивами длины n может быть между 0 (они - то же) и n* (n+1)/2 (инвертирование первого массива, каждый получает второе). Если Вы предпочитаете иметь расстояния всегда между 0 и 1, чтобы смочь сравнить расстояния пар массивов другой длины, просто разделиться на n* (n+1)/2.

Недостаток этого алгоритмы является этим время выполнения n^2. Это также предполагает, что массивы не имеют двойных записей, но это могло быть адаптировано.

Комментарий о строке кода "рассчитывает + = 1 если...": количество увеличено, только если или i-th элемент первого списка меньше, чем его j-th элемент и i-th элемент второго списка больше, чем его j-th элемент или наоборот (подразумевать, что i-th элемент первого списка больше, чем его j-th элемент и i-th элемент второго списка меньше, чем его j-th элемент). Короче говоря: (l1 [я] <l1[j] и l2 [я]> l2[j]) или (l1 [я]> l1[j] и l2 [я] <l2[j])

Немного поздно для вечеринки, но для протокола, я думаю, у Бена это почти получилось ... если бы вы дальше изучили коэффициенты корреляции, я думаю, вы бы обнаружили что коэффициент ранговой корреляции Спирмена мог быть подходящим вариантом.

Интересно, что jamesh, похоже, получил аналогичную меру, но не нормализованную.

См. этот недавний ответ SO ].