如何随机地在向量中混洗元素

Question

我正在尝试执行需要以下操作的任务:

1. 请求所需数量的元素n.
2. 使用元素0,1,2,...,n - 1填充矢量并将其显示到控制台.
3. 随机随机播放元素并将新排列显示到控制台.

我输入了矢量,但我无法弄清楚如何改变矢量.

注意:我不能使用random_shuffle函数或任何函数(除了.swap()或索引),所以不要说这样做.

到目前为止我所拥有的是什么

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

int main() {
    srand(time(NULL));
    vector<int> elements;
    int sizeOfVector;
    // size of the vector
    cout << "Please enter the size of the vector: " << endl;
    cin >> sizeOfVector;
    cout << "This is your vector:" << endl;
    // Output each element in the vector
    for (int i = 0; i < sizeOfVector; ++i) {
        elements.push_back(i);
        cout << i << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}

所以是的,再一次,我似乎无法得到的是如何在不使用random_shuffle函数的情况下将元素在不同的位置进行混洗

我尝试过使用Fisher-Yates shuffle,但它只是重复了这个向量:

for (int k = 0; k < sizeOfVector; k++)
{
    int r = rand() % sizeOfVector;
    swap(elements[k], elements[r]);
    cout << k << " ";
}

更新 感谢用户Danvil,他修复了它.

// first shuffle
for (int k = 0; k < sizeOfVector; k++) {
    int r = k + rand() % (sizeOfVector - k); // careful here!
    swap(elements[k], elements[r]);
}

// THEN print
for (int k = 0; k < sizeOfVector; k++) {
    cout << elements[k] << " ";
}

Answer 1

使用中std::random_shuffle定义的<algorithm>.看到这里.

你为什么不想使用这个功能？你的选择是复制它的源代码并命名函数my_random_shuffle- 但这显然是愚蠢的.

顺便说一句,该算法称为Fisher-Yates shuffle.

更新:您的算法实现基本上是正确的,但您需要这样做:

// first shuffle
for (int k = 0; k < sizeOfVector; k++) {
    int r = k + rand() % (sizeOfVector - k); // careful here!
    swap(elements[k], elements[r]);
}

// THEN print
for (int k = 0; k < sizeOfVector; k++) {
    cout << elements[k] << " ";
}