问题标签 [set-theory]

Set-Cover 问题包括以下内容：

鉴于：

1. 一组项目 U。

2. 一组集合 S，每个集合都包含来自 U 的项目。

求集合 C 使得：

1. C 是 S 的子集。
2. C 中的集合包含 U 中的所有项目（至少一次）。

或者，可以找到最小C，即 |C| 尽可能小。

设置封面问题的 Wiki 链接

我知道 SCP 是 NP-Complete 并且 MSCP（或 Optimal SCP）是 NP-Hard，并且可以使用多种技术中的一种来找到它（贪婪算法、遗传算法、人工神经网络）。

但是，我想问一下找到 C 的大小（即 |C|）是否也是 NP-Hard。

举个例子：

我要找|C| 没有解决问题。这是 NP-Hard 吗？如果没有，如何才能找到这个？

我在 django 中有两个模型，我不确定如何编写它们（是否有抽象模型和继承等......或者有两个不同的模型）但通常我有两种类型的对象 A 和 B。

A 和 B 完全一样，因为它们只是项目。它们都具有以下属性：

名称、价格

现在我想比较 A 和 B 中的所有相似项目（相似项目是具有相同名称的项目）并查看它们之间的价格差异（注意：假设没有重复，但假设交叉点包含可能不在的项目A 或 B 或两者都有，这意味着 A 和 B 不是相同的数据集，因此 A 可能有 20 个项目，但 B 可能有 643 个）

我如何使用模型等在 Django 中执行此操作...

我有一个模型如下：

现在我有 2 个数据源，所以我从供应商 A 获得项目，从供应商 B 获得项目。

在某些情况下，供应商 A 可能与供应商 B 的项目不同，例如供应商 A 有 30 个项目，而供应商 B 有 442 个项目，其中只有 6 个项目是常见的。通用项目被定义为具有完全相同名称的项目。

我还需要找到供应商 a 和供应商 b 物品共有的物品价格差异，这意味着供应商 a 和供应商 b 中具有相同名称的物品。我有一个很大的号码。每个供应商可能多达 10k 个项目的项目，所以需要一种有效的方法来做到这一点？

我已经检查了这个问题 获取查询集的补充。但是，它没有用。似乎它只在结果中提取一个字段。

我有以下两个表：

表A

表 B

我的目标是得到这样的补码：

补充

如何使用 ORM 得到这个结果？

模型

我有一张下表

X 列和 Y 列包含字符串，我只是举例说明了数字。

我需要这张表的输出如下

即，表中的唯一集。在第 1 行 (1,2) 和第 3 行 (2,1) 中，我只需要一组，因为 (1,2)=(2,1) 在我的集合中。类似地 (1,3)=(3,1)。所以这个表中的唯一集合是 (1,2) (1,3) 和 (3,5)。

我在 SQL 下尝试过，如果有更好的方法，请告诉我，因为我不确定是否可以将 '>' 或 '<' 与 ROWID 一起使用

http://en.wikipedia.org/wiki/Dominating_set

现在，我有个想法要找到它，我需要你的意见

第一：
在图上创建一个秩系统，每个顶点都有一个秩。顶点等级为：
2*[出边数] - [入边数]

第二：
改变DFS算法：使其也返回生成林上所有根的组（不改变复杂度）

算法：
1. 以所有顶点作为最小支配集
开始 2. 以起始顶点：排名最高的顶点运行 DFS
3. 查看生成森林上的根，获取最小支配集的列表并删除每个顶点不是生成森林上的根
4. 重复 2-3 与保留在最小支配集上的下一个最高排名的顶点
5. 当您在最小支配集上的每个顶点上运行 DFS 时停止
6. 将其返回

我使用 adj-list，所以 DFS 是 O(|V| + |E|) 你觉得这个算法怎么样？它会起作用吗？我可以做得更好吗？该算法的摊销最坏情况是什么？

我试图理解为什么集合的类别是这样定义的，单例集合作为终端对象。如果“集合”范畴包含所有可能的集合，以及这些集合之间所有可能的态射，为什么从单态集合到所有其他具有无限基数的集合没有单射、非满射态射？在这种情况下，不会有任何终端对象。

那么是什么规则导致它以定义的方式被定义，而不是用无限集和态射来定义。我想这与它是一个“具体”类别有关。但我不明白它怎么这么明显。

抱歉，如果标题错误或令人困惑。

我正在处理两个源文件（想想转换为 excel 或加载到单独的 oracle 表中的 csv 文件）。从业务角度来看，这两个文件中的数据是关联的。

文件 1 包含一组行和列。例如：

文件 2 包含类似的数据，但以未知的方式聚合：

现在显然我过度简化了很多。

我正在寻找的是一种确定文件 1 中的行如何与文件 2 中的行相关的方法。

在这种情况下，可能的结果是：

...等等...

有时有些行可能会被排除（根本不使用）。也许有使用 2x 的行。也许有 1 个协会，也许有 2 或 3 个。谁知道呢！不幸的是，数据文件的定义不是很好（在这里谈论旧的大型机系统）。

显然，我可以尝试自己手动解决，但我最终尝试了大量的组合，这些组合是死胡同，只会浪费时间。拥有一个可以接受输入并尝试查看它们可能如何相关的系统会很棒。我意识到每个可能的解决方案都需要在事后由我自己手动分析，以确保它有意义并且适用于所有数据集。

如果我正在寻找的东西是否可能，或者描述我的问题的正确术语，我将不胜感激。

如果可能的解决方案是查询形式，甚至是提供该功能的现有应用程序/程序/网站，我很好。

谢谢！

我有两个 OrderedSet，我正在尝试检查一个是否在另一个的子集中 - 元素及其顺序都很重要。然而，orderedset 包给了我奇怪的结果。

这对我来说没有任何意义，因为b包含一个69绝对不在a. 为什么是aasuperset呢b？

但是，当我尝试这个时：

这种行为对我来说似乎不一致：为什么OrderedSet中值的选择 -[433, 316, 259]与- 会影响?[1, 2, 3]issuperset()

也许有更好的方法来做到这一点？我需要知道其中的元素b是否包含在a相同的顺序中。意思是，如果

a我正在该集合中寻找以与( )相同的起始值开头的部分匹配项433。这就是我想要的：

并不是：

基本上，如果这真的令人困惑 - 我有一个有序集，我试图在值和它们的顺序方面找到部分匹配。

请考虑以下问题：

让L1和L2成为两种语言。证明或证伪下 re 语言类的封闭性

1. 区别(L1 - L2)

2. 产品(L1 x L2) （尝试在已知的假设下证明产品，其中单词L1结束以及不知道的情况。

在这里，封闭性意味着如果L1并且L2可以被旅行机器接受，那么也(L1 - L2)或(L1 x L2)

笔记

我能够找出联合和补充的解决方案（联合：封闭；补充：不封闭），但不适用于上述（差异或产品）。