Java中的Set Combinatorics算法

Question

我有一个数据集，属性如下：

Marital_status = {M,S,W,D}
IsBlind = {Y,N}
IsDisabled = {Y,N}
IsVetaran = {Y,N}

等等。大约有200个这样的变量。

我需要一个算法来生成属性的组合，一次一个值。

换句话说，我的第一个组合是：

Marital_status = M, IsBlind = Y, IsDisabled = Y, IsVeteran = Y

下一组将是：

Marital_status = M, IsBlind = Y, IsDisabled = Y, IsVeteran = N

我尝试使用一个简单的组合生成器，将每个属性的每个值视为一个属性本身。它不起作用，因为相互排斥的选择被包括在组合中，并且可能的组合的数量真的很大，准确地说是(133873417996074857185490633899939406700260683726864088366400 )

你能推荐一个算法(最好是用Java编写的)吗？

谢谢！！

Answer 1

正如其他人(以及您自己)所指出的那样，不可能对此进行详尽的测试。

我建议您采用采样方法，并使用该方法进行测试。你有很强的理论背景，所以你将能够在互联网上找到并理解这一点。

但让我举一个小例子。现在，我将忽略可能的参数“簇”(强相关)。

• 创建一个data的示例，其中包含所有200个参数的所有可能值。这种穷举确保了不会忘记任何参数值。

它不必预先创建，值可以通过循环创建。

• 对于一个数据的每个样本，您需要添加其他值。一种简单的方法是选择想要测试每个样本的次数(比如N= 100)。对于一个数据的每个样本，您将随机生成另一个values.

的N倍

如果使用全部200个参数，有1000个可能的值，以及N=100，这将给我们100K测试。

您可以通过多种方式详细阐述这一基本思想：

• 如果你希望你的测试是可重复的，你可以只生成一次，存储它，然后在以后的所有测试中重用相同的集合。
• 你可以控制你的分布，这样每个值都会被选择一定数量的真实生活，所有200个参数都不会没有连接。许多参数实际上会与其他一些参数联系在一起，因为找到这些值的概率不是偶数。而不是像我之前所做的那样，只对一个参数进行初始穷举设置，

我将在连接的parameters.集群上运行穷举集

Answer 2

找另一条路。如果你有200个变量，并且每个变量至少有2个选择，那么你将有2^200个>=组合。如果每纳秒生成一个组合，则大约需要10^43年才能枚举2^200个选项。