我有一个字母子列表列表,其中每个子列表中的字母数可以变化.列表和子列表是有序的.该结构可用于通过选择数字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个单词(只是随机英语单词).我想做得更好.