Алгоритм поиска основы набора битовых строк?
Это для утилиты сравнения, которую я пишу на C++.
У меня есть список наборов n символов -{"a", "abc", "abcde", "bcd", "de"} (, взятых из алфавита k =5 разных букв ). Мне нужен способ наблюдать, что весь список может быть построен дизъюнкциями наборов символов -{"a", "bc", "d", "e"}. То есть «b» и «c» линейно зависимы, а любая другая пара букв независима.
В версии с вращением бита -приведенные выше наборы символов -представлены как {10000, 11100, 11111, 01110, 00011}, и мне нужен способ наблюдать, что все они могут быть созданы путем объединения битовых строк из меньший набор {10000, 01100, 00010, 00001}.
Другими словами, я считаю, что ищу «дискретную основу» набора из n различных битовых -векторов в {0,1} k . В этой статье утверждается, что общая проблема является NP -полной...но, к счастью, я ищу решение только для небольших случаев(k
Я могу придумать действительно глупые алгоритмы для генерации основы. Например :Для каждой из k 2 пар букв попробуйте продемонстрировать (с помощью O(п)поиск ), что они зависимы. Но я действительно чувствую, что существует эффективный алгоритм вращения битов -, на который я еще не наткнулся. Кто-нибудь это знает?
РЕДАКТИРОВАТЬ:В конце концов, мне не нужно было решение этой проблемы. Но я все же хотел бы знать, есть ли простое битовое -решение.