c++ - 从未知集合中无放回地抽样

Question

我必须从一组我称为 S 的 DFA 中提取一致的 DFA(确定性有限自动机)。这似乎是一个简单的问题，但我没有设置S。 S 包含维度 n 的所有 DFA，因此我知道 S 的维度，我可以构建 S 但我不能，因为太大了。我也知道集合 Sm 的维度，例如 S3 是 S 的子集，S3 包含所有具有 3 个状态的 DFA，Sm 包含所有具有 m 个状态的 DFA，其中 m < n。

我没有集合 S，因此我必须模拟均匀采样。此外，我必须在不更换的情况下进行抽样。我创建了一个集合 D={1,2,3........n} 并且对于每个值，我称之为 i，在 D 我关联值 |Si|/|S| 其中 | |指示作为参数的集合中的元素数。即我创建了一个发行版。现在我可以根据这个分布从 D 中提取一个值。通过这种方式，我找到了从中提取单个 DFA 的集合。例如，如果我从 D 中提取 4，那么我必须从 S4 中统一提取一个 DFA。

但我的问题是，如何在不替换的情况下从 Si(上例中的 S4)采样 DFA？也就是说，如果我之前已经提取了一个特定的 DFA，那么在下一次采样中我必须避免使用该特定的 DFA。注意 DFA 是一个矩阵，一个表(一个二维数组)。另请注意，提取特定 DFA 意味着为上述表格的每个单元格统一提取 {1,.....,k} 中的值，其中 k 是字母表中元素的数量(您还必须提取每个状态是接受还是拒绝)。

(我必须在 C++11 中实现，但这无关紧要)

Answer 1

如果我正确理解您的问题，简单的解决方案是保留每个采样的 DFA，并在生成一个新的随机 DFA 时检查它之前是否已生成。我猜你的问题是需要大量的内存来存储它们。

如果是这样，您可以只保留每个 DFA 的哈希值 - 例如一个 128 位的 MurmurHash3，并将新生成的 DFA 的哈希值与存储的哈希值进行比较。