Алгоритм поиска минимальных элементов, необходимых для уникальной идентификации набора этих элементов

Question

Скажем, у меня есть 5 коллекций, которые содержат кучу строк (сотни строк).

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

Так что, если у меня есть

Коллекция 1:

ABC

Коллекция 2:

BBC

Коллекция 3:

CCC

Тогда коллекция 1 будет обозначена как.

Коллекция 2 будет идентифицирована с помощью BC или BB.

Коллекция 3 будет идентифицирована с помощью CC.

Существует ли уже какой-либо алгоритм, который делает подобные вещи?Название?

Спасибо, Уэсли

Answer 1

Это легко решаемая проблема.У вас есть один мультимножество (коллекция 1) (это «мультимножество», потому что один и тот же элемент может встречаться несколько раз), а затем несколько других мультимножеств (коллекция 2..N), и вы хотите найти подмножество минимального размераколлекции 1, которая не встречается ни в одной из других коллекций (2..N).

Это простая проблема, потому что она может быть решена с помощью простой теории множеств.Сначала я объясню это без использования мультимножеств, т. Е. Предположим, что каждая строка может встречаться только один раз в любом данном наборе, а затем объясню, как она работает с мультимножеством.Х ₁ .. Х _Н .Теперь, имея в виду, что на данный момент наборы не имеют нескольких экземпляров какого-либо элемента, очевидно, что любой одноэлементный набор {a} такой, что a ∉ X _i отличает S от X _i и поэтому достаточно вычислить разности множеств A - X ₁ , ..., A - X _N , а затем подобрать набор R минимального размера, такой что Rразделяет элемент со всеми этими множествами различий.Тогда это задача комбинаторной оптимизации SET COVER, которая является NP-полной, но для вашей маленькой задачи (5 коллекций) можно легко решить методом грубой силы.

Теперь, когда наборы фактически являются мультимножествами, это изменяется только так, чтоотличительные «одноэлементные» наборы на самом деле являются мультимножествами, содержащими 1 или более копий одного и того же элемента, и, следовательно, они имеют разные затраты.Вы по-прежнему можете вычислять разности наборов, как указано выше (вычитая количество элементов), но теперь ваша часть комбинаторной оптимизации SET COVER учитывает тот факт, что различающие элементы могут быть мультимножественными, а не одиночными.Вот иллюстрация, как это работает для вашей проблемы, когда мы решаем для коллекции 3:

S = {{c, c, c}}

X ₁ = {{a, b, c}}

X ₂ = {{b, b, c}}

S - X ₁ различения: {{c, c}}

S - X ₂ различителей: {{c, c}}

Минимальный мультимножество, охватывающее различитель для каждого набора: {{c,c}}

А вот как это работает для расчета для коллекции 1:

S = {{a, b, c}}

X ₁ = {{b, b, c}}

X ₂ = {{c, c, c}}

S - X ₁ Отличители: {{a}}

S - X ₂ Отличители: {{a}}, {{b}}

Минимальный мультимножество, охватывающее различитель для каждогоset: {{a}}

Answer 2

Если порядок не важен, я бы отсортировал все списки (коллекции).

Тогда вы можете посмотреть, все ли 5 ​​начинаются с одного и того же элемента.Вы бы сгруппировали их по первому элементу:

Старт - Символ вместо строк / строк.:

T A L U D
N I O S A D 
R A B E 
T A U C
D A N E B

Сортировка внутри:

A D U L T
A D O N I S
A B E R 
A C U T
A B E N D

Сортировка:

A B E N D
A B E R 
A C U T
A D U L T
A D O N I S

Сгруппированные (2):

(A B) E N D
(A B) E R 
(A C) U T # identified by 2 elements
(A D) U L T
(A D) O N I S

Остальные сгруппированы по 3 элементам:

(A C) U T     # identified by 2 elements
(A B E) N D
(A B E) R 
(A D U) L T   # only ADU...
(A D O) N I S # only ADO...

Остальные сгруппированы по 4 элементам:

(A C) U T     # AC..
(A D U) L T   # ADU...
(A D O) N I S # ADO...
(A B E N) D
(A B E R)