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

Question

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

现在我想从这些集合中的每一个中提取最少的 nr 行，以唯一标识该 1 个集合。

如果我有

集合 1:

一个乙C

集合 2:

乙乙C

集合 3:

CCC

然后集合 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

Rest 按 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...

Rest 按 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)