Shuffle Array ด้วย STL ใน C++

ที่นี่เราจะดู Shuffle และ random_shuffle ใน C++ ฟังก์ชันเหล่านี้ใช้สำหรับสลับลำดับองค์ประกอบในอาร์เรย์ เราสามารถใช้ Vector แทนอาร์เรย์ได้ การใช้งานคล้ายกัน

มาดู random_shuffle() ก่อน ใช้สำหรับจัดเรียงองค์ประกอบในช่วง [left, right) แบบสุ่ม ฟังก์ชันนี้สลับตำแหน่งของแต่ละองค์ประกอบกับตำแหน่งที่เลือกแบบสุ่ม

เราสามารถระบุฟังก์ชัน Random Generator เองได้ ถ้าไม่ระบุ จะใช้ฟังก์ชันสุ่มในตัว

ตัวอย่าง random_shuffle

#include <bits/stdc++.h>
using namespace std;

int myRandomGenerator(int j) {
    return rand() % j;
}

main() {
    srand(unsigned(time(0)));
    vector<int> arr;
    for (int j = 1; j < 20; ++j) // สร้าง 20 ตัวเลขใส่ Vector
        arr.push_back(j);
    random_shuffle(arr.begin(), arr.end()); // ใช้ random ในตัว
    cout << "arr elements:";
    for (vector<int>::iterator i = arr.begin(); i != arr.end(); ++i)
        cout << ' ' << *i;
    cout << endl;

    // ใช้ myRandomGenerator
    random_shuffle(arr.begin(), arr.end(), myRandomGenerator);
    cout << "arr elements:";
    for (vector<int>::iterator i = arr.begin(); i != arr.end(); ++i)
        cout << ' ' << *i;
    cout << endl;
}

ผลลัพธ์

arr elements: 5 14 15 6 3 16 13 12 10 2 4 1 17 9 18 11 7 8 19
arr elements: 8 10 5 6 14 1 15 3 19 16 13 18 7 9 4 12 11 17 2

ต่อไปมาดู shuffle() ฟังก์ชันนี้ก็ใช้สำหรับจัดเรียงใหม่ในช่วง [left, right) แบบสุ่ม แต่รับ Uniform Random Number Generator หนึ่งตัว

ตัวอย่าง shuffle

#include <bits/stdc++.h>
using namespace std;

main() {
    vector<int> arr;
    unsigned seed = 0;
    for (int j = 1; j < 20; ++j) // สร้าง 20 ตัวเลขใส่ Vector
        arr.push_back(j);
    shuffle(arr.begin(), arr.end(), default_random_engine(seed));
    cout << "arr elements:";
    for (vector<int>::iterator i = arr.begin(); i != arr.end(); ++i)
        cout << ' ' << *i;
    cout << endl;
}

ผลลัพธ์

arr elements: 19 7 5 6 12 4 13 3 1 17 11 14 18 2 8 15 9 10 16

ความแตกต่างระหว่าง random_shuffle() และ shuffle() คือ random_shuffle() ใช้ rand() สร้าง Index สุ่ม ส่วน shuffle() ใช้ Uniform Random Number Generator แม้ถ้าเราส่ง Uniform Random Generator ไปกับ random_shuffle() ก็จะได้ผลลัพธ์บางอย่าง