在数组中查找重叠数据

Question

我们正在编写一个C#应用程序，它将帮助去除不必要的数据重复器。只有在所有接收到的数据都被其他重复器接收时，才能移除重复器。我们需要的第一步解释如下：

我有一个整数数组集合，例如

a. {1, 2, 3, 4, 5}

b. {2, 4, 6, 7}

c. {1, 3, 5, 8, 11, 100}

可能会有成千上万个这样的数组。我需要找到可以删除的数组。只有在所有数字都包含在其他数组中的情况下，才能删除该数组。在上面的示例中，数组a可以删除，因为它的数字2和4在数组b中，并且数字1、3、5在数组c中。

最佳的做法是什么？

- genichm

---

你想要剩下的数组数量是最少的还是最小的？ - harold

这个算法需要是确定性的吗（即，无论操作顺序如何，都会给出相同的结果）？ - M. Page

数据范围总是1到100的整数吗？ - dav_i

哈罗德 - 是的，我们需要尽量少的数组。M.佩奇 - 是的。dav_i - 不，可能会有大于100的整数，在这个时刻最常见的是6位数字整数。 - genichm

@genichm 有所不同，剩余数组的最小数量是一个更难的问题（Hitting Set），可以通过迭代地删除它们来获得一些最小数量的数组。 - harold

Answer 1

这并不是针对最小剩余数组数量的优化解决方案。

为数组成员创建丰度字典。例如：

1 => 2
2 => 2
3 => 2
4 => 2
5 => 2
6 => 1
7 => 1
...

检查每个数组，如果所有成员的数量大于1，则删除该数组，并减少字典中每个数字的计数。

- Ali Sepehri.Kh

---

好主意，但创建那个字典可能不容易 :) - Selman Genç

@Ali Sepehri.Kh 谢谢 :) 我已经开始实现了。 - genichm

@genichm：祝你好运 :) 我会考虑更好的解决方案。 - Ali Sepehri.Kh

@AliSepehri.Kh，虽然这样会使它变慢，但你可以通过使用一些策略性的删除顺序（例如，“最高最小丰度的数组”）来使其对输入的顺序不那么敏感。 - harold

@harold：是的，我同意。或者包含数字1的数组应该在结果中。 - Ali Sepehri.Kh

Answer 2

获取剩余数组的最小数量（而不是不能再删除任何数组的子集）是NP难问题集合覆盖问题。然而，即使有成千上万个数组，如果将混合整数程序求解器应用于维基百科文章中的公式，很可能能够找到最优解。

- David Eisenstat