描述列表包含重复项的程度的列表的 属性 是什么？
What do you call the property of a list that describes the degree to which it contains duplicates?
我有一个函数可以选择列表的笛卡尔积，使得重复元素的数量最多：
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 的结果有 属性 的名称吗？
我相信你的函数正在计算 minimum set cover:
Given a set of elements { 1 , 2 , . . . , n } (called the universe) and a collection S of sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of S whose union equals the universe.
在你的例子中，n 是 length xss。对于 concat xss 的每个不同元素 x 在 S 中有一个集合，即集合 { i | x `elem` (xss !! i) } 出现 x 的所有索引中。然后最小集合覆盖告诉您从 xss 中的每个列表中选择哪个 x（有时会给您多个选择；任何选择将产生相同的最终小节长度）。
这是一个适用于您的 [[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].
我有一个函数可以选择列表的笛卡尔积，使得重复元素的数量最多：
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 的结果有 属性 的名称吗？
我相信你的函数正在计算 minimum set cover:
Given a set of elements { 1 , 2 , . . . , n } (called the universe) and a collection S of sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of S whose union equals the universe.
在你的例子中，n 是 length xss。对于 concat xss 的每个不同元素 x 在 S 中有一个集合，即集合 { i | x `elem` (xss !! i) } 出现 x 的所有索引中。然后最小集合覆盖告诉您从 xss 中的每个列表中选择哪个 x（有时会给您多个选择；任何选择将产生相同的最终小节长度）。
这是一个适用于您的 [[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].