有两个集合,
以下是这两个集合可能看起来像的示例:
在(
最明显的
目标是构建一个
s1
和s2
,每个集合都包含字母对。如果一对字母按相同的顺序排列,则它们等效于另一对字母,因此它们本质上是字符串(长度为2)。集合s1
和s2
是不相交的,没有一个集合是空的,并且每一对字母只出现一次。以下是这两个集合可能看起来像的示例:
s1 = { ax, bx, cy, dy }
s2 = { ay, by, cx, dx }
在(
s1
∪ s2
)中的所有字母的集合称为sl
。集合sr
是您选择的字母集,但必须是sl
的子集。您的目标是定义一个映射m
,将sl
中的字母映射到sr
中的字母,当应用于s1
和s2
时,将生成包含字母对的集合s1'
和s2'
,这些集合也必须是不相交的。最明显的
m
只是将每个字母映射到它本身。在此示例中(如下所示),s1
等同于s1'
,s2
等同于s2'
(但在给定任何其他m
的情况下,情况都不是这样)。a -> a
b -> b
c -> c
d -> d
x -> x
y -> y
目标是构建一个
m
,使得 sr
(映射右侧的字母集合)中的字母数量最少。为了实现这一点,可以将 sl
中的多个字母映射到 sr
中的同一个字母。请注意,取决于 s1
和 s2
,以及取决于 m
,你可能会违反 s1'
和 s2'
必须不相交的规则。例如,将 sl
中的每个字母映射到 sr
中的单个字母,显然会违反该规则。
因此,给定 s1
和 s2
,如何构建一个 m
,使得 sr
最小化,同时确保 s1'
和 s2'
不相交?
以下是问题的简化可视化:
s1
和s2
,因为如果您只考虑一个单一集合s = s1 ∪ s2
,问题不会改变(即,对于这个新问题的每个解决方案都是原始问题的解决方案,反之亦然)。这是否符合您的意图? - j_random_hackers1'
和s2'
是不相交的。如果我们假设只有一个输入集合s = s1 ∪ s2
,那么对s
应用m
只会生成一个输出集合s'
。问题的关键部分消失了,因为我们不再需要检查两个输出集合是否相交。所以,我认为它们不是同一个问题。 - Joshua Wisesr
的方案。因此,将每个字符映射到其本身确实是一种解决方案,但不是理想的解决方案。尽管我用字母表字母(英语中有26个字母)来陈述问题,但我正在处理的实际问题使用了256个字母的字母表。因此,存在256 ^ 256种可能的m
排列方式。我需要一个可以在真正的计算机上运行的算法,因此蛮力方法行不通。 - Joshua Wises1
和s2
是一组字符串,它们是UTF-8编码的Unicode代码点(因此在实际问题中,它们的长度可以为1-4,而不总是长度为2,但我认为这不是重要细节)。如果我能最小化m
,那么我就可以生成一个更小(因此更快;缓存未命中更少)的解析器。 - Joshua Wise