Cách xáo trộn std::vector trong C++

Việc xáo trộn vector có thể thực hiện bằng thuật toán Fisher-Yates shuffle.

Trong thuật toán này, một lần duyệt tuyến tính qua vector được thực hiện, sau đó hoán đổi từng phần tử với một phần tử ngẫu nhiên trong số các phần tử còn lại, bao gồm cả chính phần tử đó.

Thuật toán

Bắt đầu
  Khai báo hàm show().
  Truyền constructor của vector làm tham số cho hàm show().
  for (auto const& i: input)
    In giá trị của biến i.
  Khai báo v kiểu vector.
  Khởi tạo một số giá trị cho vector v theo kiểu mảng.
  Khai báo biến size kiểu integer.
  Gọi hàm size() để lấy kích thước vector.
  Gán size = v.size().
  for (int i = 0; i < size - 1; i++)
    int j = i + rand() % (size - i).
    Gọi hàm swap() để hoán đổi giá trị v[i] và v[j].
  In "Các phần tử sau khi xáo trộn".
  Gọi hàm show() để hiển trị giá trị đã xáo trộn của vector v.
Kết thúc.

Mã ví dụ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void show(vector<int> const &input) {
    for (auto const& i: input) {
        std::cout << i << " ";
    }
}

int main() {
    vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int size = v.size();
    for (int i = 0; i < size - 1; i++) {
        int j = i + rand() % (size - i);
        swap(v[i], v[j]);
    }
    cout << "Các phần tử sau khi xáo trộn" << endl;
    show(v);
    return 0;
}

Kết quả

Các phần tử sau khi xáo trộn 2 8 5 3 1 9 4 7 6