英文:
C++ shuffle algorithms
问题
我有一个作业，必须使用 rand() 或其他随机数生成器创建一个随机洗牌算法。我不能使用内置的 std::shuffle 算法，也不能使用 Fisher-Yates。是否有一些较少人知晓的洗牌算法可以实现？
对于我这个特定项目，复杂度和速度并不是太重要，所以如果有一个工作良好但复杂度很糟糕的洗牌算法，我完全可以接受。
谢谢！
英文:
I have an assignment where I must create a random shuffle algorithm using rand() or another random number generator. I cannot use the built in std::shuffle algorithm, nor can I use Fisher-Yates. Are there any lesser-known shuffle algorithms that I can implement?
Complexity and speed are not too important to me with this specific project, so if there is a shuffle algorithm that works well but has a sucky complexity that is completely fine with me.
Thank you!
答案1
得分: 2
template
struct Shufflable
{
DType data;
int random;
};
std::vector<Shufflable
...从输入的浮点数据数组初始化vec...
// 为它们分配随机值
for(auto & v:vec)
v.random = your_mersenne_twister_random_generator(); // std::mt19937
// 洗牌
std::sort(vec.begin(),vec.end(),[](auto & e1, auto & e2){ return e1.random<e2.random;});
...从vec复制浮点数据到原始数组...
assign random numbers to each element, then sort them on those random values.
If the duplicated random numbers' bias is a problem, you can improve the sorting by using the data too, or even applying a second-pass for randomization for all of the duplicates.
英文:
I would do it like this:
template<typename DType>
struct Shufflable
{
DType data;
int random;
};
std::vector<Shufflable<float>> vec;
...init vec from input float data array...
// give random values to them
for(auto & v:vec)
v.random = your_mersenne_twister_random_generator(); // std::mt19937
// shuffle
std::sort(vec.begin(),vec.end(),[](auto & e1, auto & e2){ return e1.random<e2.random;});
... copy float datas to original array from vec ...
assign random numbers to each element, then sort them on those random values.
If the duplicated random numbers' bias is a problem, you can improve the sorting by using the data too, or even applying a second-pass for randomization for all of the duplicates.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论