Выберите слова из списка так, чтобы количество уникальных букв было минимальным - PullRequest
Новая
       16

Выберите слова из списка так, чтобы количество уникальных букв было минимальным

0 голосов
/ 10 июня 2019

У меня есть список слов, из которых я должен выбрать n слов так, чтобы количество различных / уникальных букв в них было сведено к минимуму.У меня есть ощущение, что для этого уже есть известный алгоритм, но я не могу его найти.Не могли бы вы указать мне алгоритм, который можно использовать для решения этой проблемы?

Пример ниже, чтобы проиллюстрировать, что я подразумеваю под уникальными буквами

Скажем, у меня есть список слов АД, ПОМОЩЬ и НЕИСПРАВНОСТЬ,и я должен выбрать из них 2 слова.

Если я выберу АД и ПОМОЩЬ, количество уникальных букв среди них = 4

Если я выберу АД и ОТКАЗ, количество уникальных буквсреди них = 6

Если я выберу HELP и FAIL, количество уникальных букв среди них = 7

Алгоритм должен выбрать HELL и HELP.

Для моего использования-В этом случае я ожидаю, что в списках будет около 15 слов, из которых нужно будет выбрать около 9 слов.

1 Ответ

0 голосов
/ 03 июля 2019

Оптимальное решение может быть найдено с использованием модели MIP (смешанного целочисленного программирования) (или аналогичного типа моделей).

Позвольте мне быть набором букв и 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 легко доступны.

...