How to shuffle elements in a vector randomly

问题:

I'm trying to do an assignment which requires the following to happen:

1. Request the desired number of elements n.
2. Fill a vector with the elements 0, 1, 2, …, n – 1 and display it to the console.
3. Shuffle the elements randomly and display the new arrangement to the console.

I have the inputting the vector, but I cannot figure out how to shuffle the vector.

Note: I can't use the random_shuffle function or any functions (besides .swap() or indexing in this) so don't say to do that.

What I have so far is

#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;
}

So yeah, again, what I can't seem to get is how to shuffle the elements around in different positions WITHOUT using the random_shuffle function

I've tried using the Fisher-Yates shuffle, but it just repeats the vector:

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

Update Thanks to user Danvil, who fixed it.

// 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] << " ";
}

回答1:

Use std::random_shuffle defined in <algorithm>. See here.

Why would you not want to use this function? Your alternative is copy it's source code and name the function my_random_shuffle - but this is obviously silly.

By the way, the algorithm is called Fisher-Yates shuffle.

Update: Your implementation of the algorithm is basically correct, but you need to do it like this:

// 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] << " ";
}

回答2:

Use the Fisher-Yates shuffle. Your current attempt has a couple of mistakes.

For a start, this line:

cout << k << " ";

Is outputting the index, not the element. You think it is outputting the original, unshuffled vector, but that is just a coincidence due to the fact that you filled the vector with 0, ..., n - 1, which happens to be the same as the vector indexes. Change the line to:

cout << elements[k] << " ";

Your implementation is also incorrect. In Fisher-Yates, at each iteration you swap the element with one chosen at random amongst all remaining unvisited elements, including the element itself. In your implementation, you are swapping with one chosen at random from the entire vector.