c# - 点的所有有效组合，以最(速度)有效的方式

Question

我知道有很多关于生成元素组合的问题，但我认为这个问题有一定的转折性，值得提出一个新问题:

对于我的一个宠物项目，我必须预先计算很多状态，以便稍后改进应用程序的运行时行为。我挣扎的步骤之一是:

给定两个整数的 N 个元组(从这里开始我们称它们为点，尽管它们不在我的用例中。不过它们大致与 X/Y 相关)我需要计算给定规则的所有有效组合。

规则可能是这样的

• “包含的每个点都排除具有相同 X 坐标的所有其他点”
• “包含的每个点都排除 X 坐标为奇数的所有其他点”

我希望并期望这一事实会导致选择过程的改进，但我的数学技能在我打字时刚刚复活，我无法想出一个优雅的算法。

• 点集 (N) 开始时很小，但很快就超过 64 个(对于“用作位掩码”解决方案)
• 我是用 C# 做的，但如果能解释基本思想，任何语言的解决方案都应该没问题

谢谢。

---

更新以响应 Vlad 的回答:

也许我概括这个问题的想法很糟糕。我上面的规则是临时发明的，只是占位符。一个现实的规则是这样的:

• “包含的每个点都排除了所选点上方三角形中的所有其他点”

根据该规则并选择 (2,1) 我将排除

• (2,2) - 正上方
• (1,3) (2,3) (3,3) - 下一行
• 等等

所以规则是固定的，不是通用的。遗憾的是，它们比我最初提供的 X/Y 样本更复杂。

Answer 1

“包含的每个点的 x 坐标是其他包含点的 y 坐标的某个子集的精确总和”怎么样？如果您能为这个简单陈述的约束问题想出一个快速算法，那么您确实会变得非常有名。

我的观点是，所陈述的问题非常模糊，以至于承认 NP-complete 或 NP-hard 问题。约束优化问题非常困难；如果你不能对问题设置非常严格的界限，那么它很快就会变得无法在多项式时间内被机器分析。