我有一个字母子列表列表,其中每个子列表中的字母数可以变化.列表和子列表是有序的.该结构可用于通过选择数字X来生成单词,从每个子列表中的位置X取一个字母并按顺序连接它们.如果数字X大于子列表的长度,它将环绕.
给定一组单词,我需要找到一种方法将它们打包成这种最小的可能结构(即使用最短的子列表).当然,必须有与最长单词中的字母数量一样多的子列表,并且较短的单词将由空格/空格填充.
我不是CS毕业生,所以如果对问题的描述不完全清楚,我会道歉.举一个简单的例子:假设我有[ 'a ', 'an', 'if', 'is', 'in', 'on', 'of', 'i ']需要打包的单词,我可以使用以下结构:
[
[ 'i', 'o', 'a' ],
[ 's', 'n', 'f', ' ' ]
]
这将使我能够产生以下词语:
0: is
1: on
2: af*
3: i
4: os*
5: an
6: if
7: o *
8: as*
9: in
10: of
11: a
例如,如果你采取位置10,则通过连接第一个子列表中索引10%3(= 1)处的字母和来自第一个子列表的索引10%4(= 2)处的字母来生成单词"of".第二个子列表.
到目前为止,我最好的尝试是使用汉明距离矩阵来首先放置最"连接"的单词,然后放置它们最近的邻居,目标是每次插入时最小化变化.这是一个完全直观的尝试,我觉得必须有一个更好/更聪明的方法来解决这个问题.
这是我试图解决的实际问题,约束(大致)如下:
1.每个子列表的字符数应该在100或更小的区域内.
2.密钥空间应尽可能小(即虚假字的数量应该是最小的).粗略地说,数以百万计的选项中的键空间是临界的.
我不知道一个好的解决方案甚至可能.以我现在使用的算法为例,我可以在150万个选项的密钥空间中插入大约200个单词(只是随机英语单词).我想做得更好.
好吧，你说你对次优解决方案感兴趣，所以我会给你一个。这取决于字母表的大小。例如，对于 26 数组，大小将略高于 100（无论要编码的字数是多少）。
众所周知，如果有两个不同的素数a和b以及非负整数k和l( k < a, l < b)，您可以找到n数字n % a == k和n % b == l。
例如，对于 ( a = 7, a = 13, k = 6, l = 3)，您可以采用n = 7 * 13 + 7 * 3 + 13 * 6。n % 7 == 6和n % 13 == 3
对于任意数量的素数也是如此。
您可以像这样初始化数组。
['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...] # array size = 29
['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...] # array size = 31
['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...] # array size = 37
['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...] # array size = 41
...
现在，假设你的词是“极客”。为此，您需要数字 X，例如X % 29 == 6, X % 31 == 4, X % 37 == 4, X % 41 == 10。你总能找到这样的X，如上所示。
因此，如果您有 26 个字母的字母表，您可以创建宽度为 149 的矩阵（请参阅素数列表）并用它对任何单词进行编码。