问题标签 [set-theory]

让我们说我有一个男人和女人的名单。每个男人 (x) 给每个女人打分，每个女人 (y) 给每个男人打分，等级为 0-9。

例如

x1：{y1：0，y2：5，y3：9}

x2：{y1：1，y2：0，y3：9}

x3：{y1：5，y2：5，y3：8}

y1：{x1：3，x2：3，x3：5}

y2：{x1：8，x2：2，x3：2}

y3：{x1：9，x2：5，x3：9}

我正在寻找一种将所有 x 和 y 配对以最大化总收视率的算法。

在这种情况下，最佳配对将是 x2:y3 = 9+9 = 18, x1:y2 = 5+8 = 13, x3:y1 = 5+9 = 14。总评分为 45。至少我认为是肉眼可见的。

我认为它是最大独立集问题的简化版本，而不是 NP-hard 优化问题。

我有 2 个数组可以说：

我想执行以下“设置计算”：

本质上：

有没有一种聪明的方法可以做到这一点，还是我必须用循环和 ifs 交叉检查每个数组成员？我不能使用外部库（如 math.js 或 w/e）。

提前致谢。

鉴于以下代码：

我正在寻找一种方法来扭转这个过程，这样

我有一个集合列表：

我想要一组的全方位比较，即 2^n 组数：

在 Java 中执行此操作的最佳方法是什么？

例如，如果我只使用 5 套。我希望能够填充5 圈维恩图的所有重叠部分。

我正在尝试使用一组列表来做到这一点：

我想找到一些结果，例如：

本质上，我要问的是如何应用与集合并集相结合的powerset 算法。

首先：不，这不是作业！这适合我正在为游戏编写的求解器。我只是将问题简化为这个简洁的陈述：

给定一组集合 S，找出并删除 S 的任何元素，这些元素是 S 的其他元素的子集。

领域

1 <= |S| <= C^K

1 <= |S _i | <= ķ

2 <= C <= 10

10 <= K <= 500

细节

S _i是 [0, K) 的子集

min(|S _i |) >= log _C (|S|)

我目前的方法是通过我所说的“NatSet”将每个集合保持在 S 中，这只是一个bool[K]. 然后我按 |S _i |对 S 进行排序 并进行 O(|S|^2) 搜索以查找作为其他元素子集的元素。不幸的是，这对于我的目标值 C=6 和 K=16*9 来说太慢了。

这对我来说是满口的。我的挑战之一是我不知道如何提出问题——这从标题中显而易见。

我将尝试说明我的问题：

我有一张桌子，A：

和表 B：

表 B 通过ID和与表 A 相关联AID。我想构建一个具有以下过滤器的查询： Position = 1 AND Value = 4并且Position = 3 AND Value = 5它为我提供了一个不同 ID 的列表，A.ID从中 stasify所有给定的标准。

我的意思是，如果我通过 INNER JOIN 将两个表连接在一起，我只希望拥有A.ID = 12.

我自己解决这个问题的开始是这样的：

这显然行不通。我以为我有一个明确的解决方案，但当我想到它时，我真的没有。

我对这个问题有点难过，我很难寻找如何解决它的策略，因为我什至不知道在我的搜索中使用什么关键字。

我需要划分一个S={1, 2, 3, … , n}由连续数字组成的集合，使得每个子集至少有 2 个元素（规则 1）并且它由连续数字组成（规则 2）。

规则是：

1. 每个子集至少有两个元素。

2. 所有子集的所有元素都是连续的。

3. S 的所有元素都包含在分区中。

例子：

我没有在这里写下来，但是对于 n = 11 有 55 个子集组合，对于 n = 12 有 89 个子集组合。

我需要编写一个列出 n 的所有可能子集组的 Visual Basic 代码。几天来我一直在思考解决方案，但似乎问题的解决方案超出了我的能力范围。所需的嵌套循环的数量随着 n 的增加而增加，我无法弄清楚如何随着数量的增加对嵌套循环进行编程。任何帮助将不胜感激。

经过一番研究，我发现这是“所有部分 > 1 的 n 组合”的问题，并且可能组合的总数是斐波那契数（n 的 Fn-1）。

这个问题类似于“精确命中集”问题（http://en.wikipedia.org/wiki/Exact_cover#Exact_hitting_set），但约束略有不同。

我正在寻找解决以下问题的库、实现或论文。

假设我有一组集合S，并初始化如下：

S有 n 个集合，每个子集的大小未知。在这个例子中n = 4

现在我有了另一组大小为 n 的X，它被初始化为：

我需要做的是将X中的每个元素与S中的一个且仅一个集合匹配。

所以S应该对映射到X的所有集合完全满意，反之亦然。

我遇到的主要问题是如何处理S集中的重复数据。我该如何处理这些冲突？以及如何以相对可扩展的方式实现算法？

如果您有任何信息可以为我指明正确的解决方向，我们将不胜感激。

我有两张相同 K、V 类型的地图，这样

关键是国家

价值是一张地图

所以整体 Map 结构是

现在我想找出地图的哪些条目是相同的，哪些是不同的

例如：

输出应该是

有没有比遍历整个列表并逐行检查更好的方法来获取此信息（即使已经定义了这样做的方法，它也会很棒）？

我将使用它，以便我知道在过去几年中唯一改变的是少数几个城市和少数几个州。

如果需要，很乐意进一步澄清。

提前致谢。

Apologies if this question is not suited for this forum. The question extends beyond my knowledge of mathematics and programming, it is quite hard to get my head around it let alone put it in to words.

I am looking for a similar established problem from which I can construct an acceptable solution. The problem is as follows.

From a hands on perspective the problem appears similar to the traveling salesman problem, a set of interconnected nodes (network) with an associated quantifiable cost for moving from one to another. The major difference is the realization between any two paths potentially changes the cost of all subsequent steps, removes possible paths or in some cases removes nodes completely from the network.

I want to, in a reasonable amount of time, find a path or small collection of paths which is close to the best starting from any node, best being defined as the path which produces the lowest value from the equation [cost / total nodes travelled].

The obvious answer would be to permutate over all paths however this is not realistic possible given the potential number of nodes and the nature of the networks.

For those wondering about the real world problem it goes as follows.

I have sets with a cardinality of 8, each item in the set has a value of 0-15. These sets are grouped in groups of 8. They have been grouped so that between all 8 sets a minimal amount of possible values 0-15 is used (typically the group of 8 sets will use between 6-8 of the possible 0-15 numbers with a few outliers each way).

Each of these groups has a transformation table which allows me to replace the real value in a set with a reference to the value, these transformation tables are 16 entries long.

This creates the opportunity to represent multiple sets with the same pattern of variance with a single set and allow the transformation tables to realize their real respective values.

[ 7, 7, 9, 9] [ 4, 4, 5, 5]

Becomes

[ 1, 1, 2, 2] with respective transformations (1=7, 2=9) (1=4, 2=5).

Of course as sets in a group get transformed they eat up entries in the transformation table reducing the ability for further transformations to occur. In the network problem the cost is associated with the number of additional entries I need to realize a transformation and the removal is when a transformation is no longer possible.

Additional factors to consider...

• if a value(s) in a both sets can be represented using an existing transformation entry (they need to correspond to the same entry in the table (7=value in set 1, 7=value in set 2) then the cost of those value(s) is free.
• entries in the transformation table that extend beyond the total individual numbers used in a group of sets can be used as wild cards (basically the transformation table can reference the same value multiple times as long as their remains enough entries to create at least one reference for all values).
• Each possible original value must be referenced in the transformation table at least once (obviously we need to be able to reference it to reproduce the original set).

I am aware computational complexity theory and the fact that I am seeking an approximation or heuristic solution. Ideally from my knowledge of the cost between nodes and knowledge of possible connections I would like to create a small subset of paths from which I can test and take the best.