c++ - 如何使用 STL 对数组进行 k-shuffle？

Question

我正在测试一种对 k 排序数组进行排序的算法(每个元素最多偏离其正确排序位置的 k 个位置)。

我很难生成测试数据 -- 我无法通过 k 位置随机交换元素，因为我最终可能会交换一个元素两次。我可以跟踪我交换了哪些元素，但我需要 O(N) 空间。我也可以使用大小为 k + 1 的随机堆，但这听起来很傻。

STL 中是否有任何内置功能可以帮助我解决这个问题？这似乎是一个常见问题，但我的简短研究只发现了总洗牌算法(我认为 STL 实现了 Fisher-Yates)。

Answer 1

这感觉很奇怪，因为准备随机测试数据不需要非常高效，而且数据通常可以是任何东西。您可以将测试值作为那些给出正确位置范围的元素或对的正确位置。例如对数组:

1. 1,1
2. 2,4
3. 2,4
4. 2,4
5. 5,6
6. 5,6
7. 7,7
   ...

将随机生成器的状态存储在某处。

随机选择两个距离other的原始位置(或范围)不超过k个位置的元素并交换。重复 N 次，您的测试数据就准备好了。

如果您以后需要获得相同的序列，则恢复随机生成器状态并重复该算法。