Как проверить (нетривиально) эквивалентность списков чисел, быстро?

У меня есть список целых чисел, например 1,2,2,3,4,1 . Мне нужно иметь возможность проверять эквивалентность (==) между разными списками.

Однако я не имею в виду простое сравнение с числовым подходом. Каждый из этих списков фактически обозначает раздел набора, где позиция в списке обозначает индекс элемента, а число обозначает индекс группы. Например, в первом случае элемент 0 и элемент 5 находятся в одной группе, элементы 1 и 2 находятся в одной группе, а элементы 3 и 4 находятся в своих индивидуальных группах. Фактический индекс группы не важен, важна только группировка.

Мне нужно иметь возможность проверить эквивалентность в этом смысле, поэтому, например, предыдущий список будет эквивалентен 5,3,3 , 2,9,5, , поскольку они имеют одну и ту же группировку.

То, как я делал это, сводило массив к некоторой нормальной форме. Затем я продолжаю работу в списке, пока не найду новое число, найду все числа с одинаковым значением this и установлю их все на 1. Я продолжаю таким же образом.

В моем примере оба числа уменьшились бы до уменьшились бы вниз на 0,1,1,2,3,0 и, конечно же, я могу просто использовать простое сравнение, чтобы увидеть, эквивалентны ли они.

Однако это довольно медленно, так как я должен сделать несколько линейных проходов по списку. Итак, чтобы перейти к делу, есть ли более эффективный способ приведения этих чисел к этой нормальной форме?

Как бы то ни было, в более общем плане, могу ли я избежать этого сокращения и сравнивать массивы в разных и возможно более эффективным способом ?

Детали реализации

• Эти массивы фактически реализованы как битовые наборы для экономии места, поэтому мне действительно приходится каждый раз перебирать весь список, так как хеширование rb_tree esque не выполняется.
• Large номера этих массивов будут хранится в stl unordered_set, следовательно необходимо учитывать требование хэша