Сравнение наборов подмножеств с точностью до перестановки

Question

У меня есть массив a [i] [j]. Элементы являются char, интерпретируются как подмножества множества {1, ..., 8} (элемент k находится в подмножестве, если k-й бит равен 1). Я не думаю, что это актуально, но каждый элемент имеет ровно 4 бита.

Каждая строка a [1] [j] .. a [n] [j] представляет собой набор подмножеств {1, ..., 8}. Мне нужно удалить повторяющиеся строки, где две строки считаются дубликатами, если их можно получить из другой путем перестановки {1, ..., 8}.

Пример (0bxxxxxxxx означает двоичное число):

0b11000000, 0b01100000, 0b00110000 

является дубликатом

0b00110000, 0b00011000, 0b00100100 

поскольку первые может быть получен из последнего путем применения перестановки

8->8, 7->7, 6->1, 5->4, 4->3, 3->2, 2->5, 1->6 

и переупорядочение результата.

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

Благодарим за помощь.

Answer 1

Если все подмножества имеют 2 элемента, это будет представлять graph isomorphism с подмножествами, представляющими графы графа. Это еще более общий (возможно, более сложный), поэтому я бы посмотрел на эвристику, используемую для решения изоморфизма графа, и посмотрим, применимы ли они здесь.

Существует много эвристики графоизоморфизма, которые могут дешево исключать изоморфизм. Для конкретной коллекции вы можете вычислить, сколько подмножеств принадлежит каждому элементу, а затем сортировать. В вашем примере обе коллекции получат [2,2,1,1,0,0,0,0]. Если отсортированные последовательности для двух наборов различны, то изоморфизм отсутствует. Конечно, равенство не гарантирует, что есть.

Есть еще много аналогичных эвристик, которые еще лучше при просеивании неизоморфных графов (и могут применяться здесь).

Кроме того, 8! это всего лишь 40320, поэтому грубое форсирование всех перестановок не является абсолютно неосуществимым.