Сравнить поворотные списки, содержащие дубликаты

Question

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

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

Например, [9, 2, 0, 0, 9] и [0, 0, 9, 9, 2] это результаты,
, где [9, 0, 2, 0, 9] не будет (так как заказ отличается).

Это пример эффективной работы, которая работает.

def min_list_rotation(ls): 
    return min((ls[i:] + ls[:i] for i in range(len(ls)))) 

# example use 
ls_a = [9, 2, 0, 0, 9] 
ls_b = [0, 0, 9, 9, 2] 

print(min_list_rotation(ls_a) == min_list_rotation(ls_b)) 

Это может быть улучшен для повышения эффективности ...

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

Однако ее по-прежнему не очень эффективный метод, так как он основан на проверке много возможностей.

Есть ли более эффективный способ выполнить это сравнение?

---

Связанный вопрос: Compare rotated lists in python

Answer 1

Если вы ищете дубли в большом количестве списков, вы можете вращать каждый список его лексикографический минимальному строковое представление, а затем отсортировать список списков или использовать хэш-таблицу, чтобы найти дубликаты. Этот шаг канонизации означает, что вам не нужно сравнивать каждый список со всеми другими списками. Существуют умные алгоритмы O (n) для поиска минимального вращения, описанного в https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation.

Answer 2

У вас его почти есть.

Вы можете сделать своего рода «нормализации» или «canonicalisation» списка независимо от других, то вам нужно только сравнить по пунктам (или, если вы хотите, поместить их в карту, в наборе для устранения дубликатов, ..."

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

В вас пример 92009, вы должны сделать первый 0 (а не второй)

2 Если у вас есть всегда один и тот же предмет (скажем, 00000), вы просто держать, что: 00000

3 Если у вас есть тот же самый пункт несколько раз, возьмите следующий элемент, который является мини и продолжайте идти, пока не найдете один уникальный путь с минимумами.

Пример: 90148301562 => у вас есть 0148 .. и 0156 .. => вы берете 0148

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

Пример: 014376501437650143765: у вас есть один и тот же шаблон 0143765 ...

Это как AAA, где A = 0143765

5 Если у вас есть свой список в таком виде, это легко сравните два из них.

Как сделать это эффективно:

итерации в списке, чтобы получить минимумы Mx (не предшествовал сам по себе). Если вы найдете несколько, сохраните их все.

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

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

Надеюсь, что это поможет.

Answer 3

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

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

Это работает так:

Допустим B имеет N элементов, то хэш B, используя простое Р:

Hb=0; 
for (i=0; i<N ; i++) 
{ 
    Hb = Hb*P + B[i]; 
} 

Это оптимизированный способ оценить полином P, и равнозначно:

Hb=0; 
for (i=0; i<N ; i++) 
{ 
    Hb += B[i] * P^(N-1-i); //^ is exponentiation, not XOR 
} 

Обратите внимание, что каждый B [i] умножается на P^(N-1-i). Если мы сдвинем B налево на 1, то каждый каждый B [i] будет умножен на дополнительный P, кроме первого.Поскольку умножение распределяется по сложениям, мы можем сразу размножить все компоненты, просто умножив весь хэш, а затем зафиксируем коэффициент для первого элемента.

Хэш левого сдвига B просто

Hb1 = Hb*P + B[0]*(1-(P^N)) 

Второй сдвиг влево:

Hb2 = Hb1*P + B[1]*(1-(P^N)) 

и так далее ...