用于查找唯一标识这些元素集合所需的最小元素的算法

Question

假设我有5个包含一堆字符串的集合(数百行).

现在,我想从每个集合中提取最少的行数,以唯一地标识该集合.

所以,如果我有

收集1:

A B C.

收集2:

B B C.

收集3:

C C C.

然后收集1将由A识别.

集合2将由BC或BB识别.

收集3将由CC识别.

是否有任何算法可以做这种事情？名称？

谢谢,韦斯利

Answer 1

如果顺序不重要，我会对所有列表（集合）进行排序。

然后你可以看看这 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)