как определить, отличаются ли две последовательности перестановкой?

Question

Учитывая любые две последовательности из n действительных чисел, скажем, (a1, a2, ..., an) и (b1, b2, ..., bn), как определить, существует ли одна последовательность (которую также можно рассматривать каквектор) является перестановкой другого?

Я планирую разработать алгоритм и запустить его на Matlab, чтобы выполнить эту работу.Я могу думать только об алгоритме, который стоит n!раз: просто попробуйте все перестановки в п.

Есть ли более быстрый алгоритм?

Answer 1

Прежде всего, почему п!?если для каждого ai вы ищете совпадение в bi, вы получите O (n ^ 2).В любом случае более эффективно использовать сортировку со сложностью O (nlogn).

A=[3,1,2,7];
B=[2,3,1,7];
isPermutated=isequal(sort(A),sort(B))

Answer 2

Просто отсортируйте обе последовательности и сравните отсортированные результаты.

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