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

Question

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

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

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

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 элемента, это представляло бы изоморфизм графов, с подмножествами, представляющими ребра графа.Это еще более общий подход (поэтому, вероятно, более сложный), поэтому я бы посмотрел на эвристики, используемые для решения изоморфизма графов, и посмотрел, применимы ли они здесь.

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

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

А еще 8!составляет всего 40320, поэтому перебор всех перестановок не является полностью невозможным.