一个列表包含的重复元素程度被称为什么属性？

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的结果有一个名称吗？

- marc_r

---

我不确定，但在这种情况下，你也可以说一些关于“基数”的事情，例如“字母表具有最低基数的序列”。但我想那比“包含最多重复项”更糟糕... - jberryman

我写了一个提议“多重性”的答案，但后来意识到我并不真正理解这个问题。（例如，[1,4,1,4]比[1,1,1,4]有更多的“重复项”吗？为什么（不是）？）即便如此，您可能会喜欢在维基百科上阅读有关该词的内容，看看它是否与您相关。 - Daniel Wagner

@jberryman，这样做实际上更好，因为它积极强调了我想要的属性。当你说“字母表”时，我也意识到可以用列表操作来表达。我可能想使用术语“投影”。 - marc_r

@DanielWagner，“Multiplicity”听起来很抓人。如果我将我的列表解释为多重集合，我认为它非常贴切。[1,4,1,4]和[1,1,1,4]一样好（它们的“nub”长度相同），所以我想要类似于“总重复度”的东西。更具体地说，我在生成某些图形时使用它，其中我希望尽可能合并尽可能多的相同节点。 - marc_r

“同质性”？或者熵，就像Shannon定义的那样，如果您将列表视为变量的可能值。 - Jean-Baptiste Potonnier

@Jean-BaptistePotonnier [1,4,1,4] 和 [1,1,1,4] 的熵是不同的，尽管我认为它们相等。 - marc_r

Answer 1

我相信您的功能是计算最小集合覆盖：

给定一个元素集{1，2，...，n}（称为宇宙）和一个集合S，其并集等于宇宙，集合覆盖问题是要确定其并集等于宇宙的最小子集合S。

在您的情况下，n是length xss。对于concat xss中的每个不同元素x，S中都有一个集合，即所有出现x的索引的集合{i|x 'elem'（xss !! i）}。然后最小集合覆盖告诉您从xss中选择哪些x（有时会给出多个选择；任何选择都将产生相同的最终nubbed长度）。

这里是您的[[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]。

- Daniel Wagner

---

太棒了。从维基百科的链接中，我理解到我的函数实际上是解决了“命中集问题”，这是通过在最小集覆盖问题中交换集合和宇宙来实现的。这正是你在这里所做的。 - marc_r