我正在测试一种对 k 排序数组进行排序的算法(每个元素最多偏离其正确排序位置的 k 个位置)。
我很难生成测试数据 -- 我无法通过 k 位置随机交换元素,因为我最终可能会交换一个元素两次。我可以跟踪我交换了哪些元素,但我需要 O(N) 空间。我也可以使用大小为 k + 1 的随机堆,但这听起来很傻。
STL 中是否有任何内置功能可以帮助我解决这个问题?这似乎是一个常见问题,但我的简短研究只发现了总洗牌算法(我认为 STL 实现了 Fisher-Yates)。
最佳答案
这感觉很奇怪,因为准备随机测试数据不需要非常高效,而且数据通常可以是任何东西。您可以将测试值作为那些给出正确位置范围的元素或对的正确位置。例如对数组:
- 1,1
- 2,4
- 2,4
- 2,4
- 5,6
- 5,6
- 7,7
...
将随机生成器的状态存储在某处。
随机选择两个距离other的原始位置(或范围)不超过k个位置的元素并交换。重复 N 次,您的测试数据就准备好了。
如果您以后需要获得相同的序列,则恢复随机生成器状态并重复该算法。
关于c++ - 如何使用 STL 对数组进行 k-shuffle?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35275901/