0

我有一堆套，A1，A2，A3，... AN。每组包含从 0 到 2000 的值的 N 个元素（可以说最大 1000 个）。例如。

A1{1,2,3,4}
A2{2,4,3,5}
A3(1,2,5,6)

现在对于尺寸 k，例如 3，A1 的组合将是 C1(1,2,3), C2(1,2,4), C3(2,3,4) 对于 A1 到 AN 我需要弄清楚如果 A1 中的所有组合也存在于 A2 到 AN 的组合中。

即A1 的组合C3 将匹配A2 中的组合，并且可能匹配AN。现在我需要 A1 的 C1 和 C2 的结果以及 A2 到 AN 的结果。简单而低效的方法是为所有集合 A1 到 AN 生成所有 k 大小的组合。然后对于 A 的 C1 哪里/如果它存在于 A2 到 AN。之后是 C2，然后是 C3。然后继续下一组并重复。

我该如何改进这种方法，因为一旦添加了新集合，它就需要频繁且昂贵的计算？

我发现的另一种解决方案将在 O(N^2 + N) 中运行而不进行优化，这基本上涉及获取 A1 和 A2...AN 的交叉点，计算这些交叉点的​​组合，然后查看每个组合的次数发生在生成的结果中。

4

1 回答 1

0

您可以尝试散列您的组合。您可以在这里使用两种方法，一种优化空间，另一种优化时间。对于时间优化，您的散列函数将为每个组合创建一个唯一键，并且每当您在一个已经被占用的地方被击中时，您就会知道您不是第一次遇到该组合。对于空间优化，方法类似，但密钥不是唯一的。您必须管理与该键对应的组合列表，并在点击时遍历它以查看它是否包含您当前正在检查的组合。您的密钥的唯一性等级将定义您的表的大小，因此您将不得不花费时间来验证命中。

于 2012-11-03T06:14:45.520 回答