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

Question

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

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

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

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

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

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

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

Подробности реализации

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

Answer 1

Попробуйте выполнить итерацию по двум последовательностям параллельно, сохраняя карту (либо std::map, либо массив) от значений в первом массиве до значений во втором и наоборот. Если вы попадаете в пару, которой нет в вашей таблице, добавьте ее, если в таблице нет чего-либо для этого первого или второго числа (поскольку это будет указывать на неравенство). Например:

1,2,2,3,4,1
5,3,3,2,9,5

Вы бы добавили 1-> 5, 2-> 3, 3-> 2 и 4-> 9, и сравнение прошло бы. Для чего-то немного другого:

5,3,3,2,9,5
1,2,2,3,2,1

вы бы добавили 5-> 1, 3-> 2, 2-> 3, затем 9-> 2 потерпит неудачу, поскольку во второй последовательности уже есть привязка для 2; Таким образом, вы знали бы, что последовательности не были эквивалентны.

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

Answer 2

Для алфавита из K символов и массива из N этих символов вы сможете создать подпись (или каноническое представление ) массива в O(N), используя хеш-таблицу, или в O(N log K), используя двоичное дерево поиска.

Хитрость заключается в том, чтобы выполнить преобразование всех цифр за один проход:

std::unordered_map<std::size_t,std::size_t> map;

std::vector<std::size_t> signature;
signature.reserve(array.size());

for (std::size_t i: array) {
  // insert only inserts if they key is not already present
  // it returns std::pair<iterator,bool> with iterator pointing
  // to the pair {key: i, value: index}
  size_t index = map.insert({i, map.size()}).first->second;
  signature.push_back(index);
}

Хэш массива - это хеш его подписи .

Но, что более важно, нет причины не ставить все массивы в их каноническое представление раз и навсегда .

Answer 3

Вы можете переопределить алгоритм хеширования и создать ключ хеша, который уникально кодирует группировку.Таким образом, когда каждый массив вставляется в хеш-таблицу, все массивы с одинаковой кодировкой группы будут объединены в одно и то же место хеширования.После того, как все массивы будут вставлены, массивы будут уже сгруппированы.

Возможное кодирование может быть: [1 2 2 3 4 1] хешируется до 162345. (Гм ... извините, кодировка не уникальна).

Нам нужна уникальная кодировка, поэтому нам нужно записать как положение, так и количество групп в массиве.Так как насчет

[1 2 2 3 4 1] -> 1622324151 (слева направо, групповые обозначения, за которыми следует заданное количество элементов)

[5 5 5 9 9 9]-> 12334563

[1 2 3 4 5 6] -> 112131415161

Я уверен, что есть более умные кодировки, но это будет очень быстрый хеш.

Пол

Answer 4

Если вы знаете максимально возможную «группу», то вы можете сделать что-то вроде этого (psuedocode, но вы должны быть в состоянии понять это:)

for i = 0; i < listLength; i++
    if !mapping[list1[i]]
        mapping[list1[i]] = list2[i]
    if mapping[list1[i]] != list2[i]
        return false;
return true;