时间戳

首页 > 解决方案 > 从列表中选择单词，使唯一字母的数量最少

algorithm - 从列表中选择单词，使唯一字母的数量最少

问题描述

我有一个单词列表，我必须从中选择 n 个单词，以便将其中不同/唯一字母的数量保持在最低限度。我有一种感觉，已经有一个众所周知的算法，但我找不到它。可以指出可以用来解决这个问题的算法吗？

下面的一个例子来说明我所说的独特字母的意思

假设我有 HELL、HELP 和 FAIL 的单词列表，我必须从中选择 2 个单词。

如果我选择 HELL 和 HELP，其中唯一字母的数量 = 4

如果我选择 HELL 和 FAIL，其中唯一字母的数量 = 6

如果我选择 HELP 和 FAIL，其中唯一字母的数量 = 7

该算法应选择 HELL 和 HELP。

对于我的用例，我希望有大约 15 个单词的列表，必须从中选择大约 9 个单词。

标签： algorithmminimization

解决方案

可以使用 MIP（混合整数规划）模型（或类似类型的模型）找到最佳解决方案。

设 i 是字母集， w 是单词集。此外，定义二进制变量：

x(w) = 1 if word w is selected 
       0 otherwise

y(i) = 1 if letter i is selected 
       0 otherwise

然后我们可以写：

min sum(i, y(i))
subject to
    sum(w,x(w)) = K
    y(i) >= x(w)  for letters i in word w
    y,z in {0,1}

当我解决这个问题时，我看到以下内容。

数据组织如下：

----      8 SET i  letters

A,    B,    C,    D,    E,    F,    G,    H,    I,    J,    K,    L,    M,    N,    O,    P,    Q,    R,    S,    T
U,    V,    W,    X,    Y,    Z


----      8 SET w  words

HELL,    HELP,    FAIL


----      8 SET map  

               A           E           F           H           I           L           P

HELL                     YES                     YES                     YES
HELP                     YES                     YES                     YES         YES
FAIL         YES                     YES                     YES         YES

----      8 PARAMETER k                    =        2.000  number of words to select

解决方案如下所示：

----     29 VARIABLE x.L  select word

HELL 1.000,    HELP 1.000


----     29 VARIABLE y.L  selected letters

E 1.000,    H 1.000,    L 1.000,    P 1.000


----     29 VARIABLE z.L                   =        4.000  objective

MIP 求解器很容易获得。

推荐阅读