选择唯一组合的算法

Question

我正在寻找解决这个问题有用的算法或方法：

假设我有一个数据框：

       x         y    Bin1  Bin2      Bin3 
153.0303 -27.17894      10         6         5        
153.0303 -27.17916       8         7         8        
153.0303 -27.17938       1         6         3        
153.0300 -27.17960      10         1         8     

这个数据集有大约10k行。每个Bin可以是1到10的整数。我想做的是选择一个随机子集，其中每个Bin只有唯一的值。例如，这个数据框是有效的，因为每个Bin都有10个不同的值。

       x         y    Bin1  Bin2      Bin3 
153.0303 -27.17894       1         6         4        
153.0303 -27.17916       2         7         2        
153.0303 -27.17938       3         5         3        
153.0300 -27.17960       4         3         8    
153.0303 -27.17938       5         4         1        
153.0300 -27.17960       6         8         7  
153.0303 -27.17938       7         1         6        
153.0300 -27.17960       8         2        10  
153.0303 -27.17938       9         10        5        
153.0300 -27.17960      10         9         9   

我目前的方法是反复随机选择行，直到找到一种组合。然而，我正在尝试找到一种更有效的方法。

提前感谢您！

- Loleman

---

如果箱子的值是随机的，我认为你不能比随机选择更好。如果它们按某种方式排序，也许可以利用这一点使算法更有效率。 - Caridorc

请尝试使标题更加精确和具体，以便解决您的问题。 - Caridorc

只需选择大小为1的子集，它们总是具有唯一值。 - Kelly Bundy

Answer 1

想法：我们跟踪两个索引：当前和最后。任何在 current 之前的内容都是我们正在构建的集合的一部分，而在 last 之后的所有内容都已被排除，因为它们与我们的集合中的某些内容不兼容。

我们还为每个 bin 保留一组无效值。

用当前值设置为1和last值设置为n(行数)进行初始化。

1. 将 row[current] 与介于 current 和 last 之间（包括 current 和 last）的随机行交换。
2. 如果交换的行有效（根据你的集合检查），则更新你的集合，增加 current，并返回到1，或者如果达到目标则停止。
3. 如果交换的行无效，则将其与最后一行交换，减少 last，并返回到1。

在最糟糕的情况下，您要求的是不可能实现的事情。即，您想要 k 个有效行，但有效行的最大集合大小 < k。在这种情况下，您将运行 n 次此循环。

也有可能您请求 k 个有效行，它们存在，但您已经选择的 k-1 行或更少行与任何行添加都不兼容。

因此，这种方法是否合理取决于您的数据。

- Dave