Что вы называете свойством списка, который описывает степень, в которой он содержит дубликаты?

Question

У меня есть функция, которая выбирает декартовы произведения списков так, чтобы количество повторяющихся элементов было наибольшим:

import Data.List (nub)

f :: Eq a => [[a]] -> [[a]]
f xss = filter ((==) minLength . length . nub) cartProd
  where
    minLength = minimum (map (length . nub) cartProd)
    cartProd = sequence xss

Например:

*Main> f [[1,2,3],[4],[1,5]]
[[1,4,1]]

Но:

*Main> sequence [[1,2,3],[4],[1,5]]
[[1,4,1],[1,4,5],[2,4,1],[2,4,5],[3,4,1],[3,4,5]]

Есть ли имя для свойства, которое имеет результат моей функции f?

Answer 1

Я считаю, что ваша функция вычисляет минимальный набор покрытия:

Дан набор элементов { 1, 2, .,,, n } (называемый юниверсом) и набор S наборов, объединение которых равно юниверсу, проблема покрытия множеств состоит в том, чтобы идентифицировать наименьшее подмножество S, объединение которого равно юниверсу.

В вашем случае n это length xss, Существует один набор в S для каждого отдельного элемента x из concat xssа именно набор { i | x `elem` (xss !! i) } всех показателей, которые x происходит в минимальной обложке, а затем говорит вам, какие x выбрать из каждого списка в xss (иногда дает вам несколько вариантов; любой выбор даст одинаковую конечную длину).

Вот рабочий пример для вашего [[1,2,3],[4],[1,5]]:

Вселенная {1,2,3}.

В коллекции S пять комплектов; Я назову их от S_1 до S_5:

• S_1 = {1,3}, поскольку первый и третий списки содержат 1.
• S_2 = {1}, потому что первый список содержит 2.
• S_3 = {1}, потому что первый список содержит 3.
• S_4 = {2}, потому что второй список содержит 4.
• S_5 = {3}, потому что третий список содержит 5.

Минимальная установленная крышка для этого - {S_1, S_4}. Поскольку это набор обложек, это означает, что каждый список содержит 1 или же 4, Поскольку он минимален, никакой другой выбор наборов не создает меньшую конечную коллекцию значений. Итак, мы можем выбрать либо 1 или же 4 из каждого списка, чтобы получить окончательный ответ. Как это бывает, ни один список не содержит 1 а также 4 так что есть только один выбор, а именно [1,4,1],