Làm cách nào để tạo ngẫu nhiên một hàm số ánh xạ song ánh (bijection mapping function) không trùng lặp giá trị?

MeigyokuThmn · November 26, 2018, 7:24am

Nhu cầu của mình là về việc rút ngẫu nhiên phần tử từ một tập hợp, ví dụ mảng, ở đây do rút từ mảng cho nên không bao giờ có chuyện random trùng nhau (nếu các phần tử trong mảng đều unique).
Ví dụ về việc, ờ viết bot cho Discord chẳng hạn, làm 1 lệnh kiểm tra trắc nghiệm, mình có 1 mảng các câu hỏi, mỗi câu hỏi có 1 mảng đáp án khả dĩ.
Vì vậy khi user gọi lệnh trắc nghiệm, con bot phải xáo trộn thứ tự câu hỏi, và xáo trộn cả thứ tự các đáp án khả dĩ để in ra cho user lựa chọn, ví dụ ta có kho câu hỏi như sau:

let questions = [
   { text: "Thủ đô của Hà Nội là gì?", answers: [
        ['Hà Nội', true], ['TPHCM', false], ['Nha Trang', false], ['Huế', false]
   ]},
   { text: "Trái Đất có bao nhiêu đại dương?", answers: [
        [5, true], [4, false], [3, false], [2, false]
   ]},
   { text: "Việt Nam là đất nước có khí hậu gì là chủ đạo?", answers: [
        ['Nhiệt đới', true], ['Ôn đới', false], ['Hàn đới', false],
   ]},
]

Thì con bot sẽ in ra lần lượt không theo thứ tự 2 câu ngẫu nhiên không trùng nhau trong 3 câu hỏi trên, các đáp số khả dĩ thì cũng sẽ được in ra không theo thứ tự, user có thể nhập A, B, C hoặc D để lựa chọn.

Như vậy trong quá trình trắc nghiệm, con bot phải tích lũy 1 trạng thái ứng với user đó, trạng thái ở đây là để biết được user đó đang làm trên tập hợp ngẫu nhiên nào, với các đáp án được ngẫu nhiên theo thứ tự nào. Hiện tại mình không muốn sử dụng session hay db gì hết, mình cũng không thể xáo trộn vào mảng gốc vì có nhiều người còn làm bài.

Vậy có 2 hướng xây dựng trạng thái cho mỗi user:

Clone ra 1 subset của tập hợp các câu hỏi, xáo trộn bản clone đó và xáo trộn luôn các mảng đáp án trong từng câu hỏi trong bản clone đó, như vậy mỗi một user khi làm trắc nghiệm sẽ có 1 bản clone như vậy, cách này hơi tốn bộ nhớ;
Xây dựng ngẫu nhiên cho mỗi user một hàm số ánh xạ song ánh, cách này rất nhẹ nếu làm được.

Hàm số song ánh là như thế này: ví dụ cho tập hợp A = {1, 2, 3, 4, 5}, ta xáo trộn A ra tập hợp B = {2, 4, 5, 3, 1}, ta có f(A) = B là hàm song ánh.
Tức là index 1 tương ứng với index 2, index 2 tương ứng với index 4, v.v.

Ý tưởng của mình là xây dựng ngẫu nhiên một hàm song ánh để thỏa mãn tính chất như trên, chỉ cần đưa 1 index cụ thể vào f(A) là nó sẽ cho mình index của B, nếu cho hết index của A vào f(A) thì sẽ ra các index của B mà không hề bị trùng lặp.

Ví dụ về code mong muốn (mình không muốn làm cùng một lúc ra B hoàn chỉnh, mình chỉ muốn có subset của B)

let seed = Math.random();
let A = [1, 2, 3, 4, 5];
let bijectionMap = randomlyBuildBijectionMappingFunction(seed, A.length)
for (let index = 0; index < 3; index++)
   console.log(A[bijectionMap(index)])

Output

4
3
5

Hoặc

1
5
3

Hoặc

2
5
4

Nhờ các cao thủ toán học vào giúp mình với ạ.

tntxtnt · November 26, 2018, 12:56pm

xài Reservoir sampling :V

Facebook xài reservoir sampling nè: https://youtu.be/YA-nB2wjVcI?t=1241

code khéo 1 tí thì cũng ko cần tạo mảng A đâu :V Cần mảng B k phần tử thôi

edit: code cũ: https://rextester.com/DLY27830

#include <algorithm>
#include <chrono>
#include <iostream>
#include <numeric>
#include <random>
using namespace std::chrono; //"tác giả" thư viện chrono cũng thường xuyên bỏ
                             //qua namespace std::chrono

// lấy k số ngẫu nhiên có giá trị trong đoạn [min, max]
template <class URBG>
std::vector<int> generate_random_numbers(int k, int min, int max, URBG&& g)
{
    std::vector<int> ret(k);
    std::iota(begin(ret), end(ret), min);
    for (int n = max - min + 1, i = k; i < n; ++i)
    {
        int j = std::uniform_int_distribution<int>{0, i}(g);
        if (j < k) ret[j] = min + i;
    }
    return ret;
}

int main()
{
    // tương tự như seed = time(NULL)
    // duration_cast<seconds> cast nanoseconds/milliseconds về seconds
    // system_clock::now() trả về thời điểm hiện tại
    //.time_since_epoch() trả về quãng thời gian giữa thời điểm gọi nó và mốc
    //thời điểm đầu tiên (epoch) .count() lấy ra giá trị của quãng thời gian (ở
    //đây là số nguyên có đơn vị là giây)
    auto seed =
        duration_cast<seconds>(system_clock::now().time_since_epoch()).count();
    std::cout << "seed = " << seed << "\n";

    // tạo 1 random engine, ở đây là mt19937 pseudo random bit generator (prbg)
    std::mt19937 prbg;
    // rồi seed nó với `seed` ở trên
    // nếu ko muốn seed theo thời gian, có thể xài boost::random_device
    //  prbg.seed(boost::random_device{}());  //#include
    //  <boost/random/random_device.hpp>
    // hoặc std::random_device trên MSVC 2017
    //  prbg.seed(std::random_device{}());    //MSVC 2017
    prbg.seed(seed);

    // tạo 1500 số ngẫu nhiên có giá trị từ 1 tới 5000
    auto arr = generate_random_numbers(1500, 1, 5000, prbg);
    for (int n : arr) std::cout << n << ' ';
}

noz1995 · November 26, 2018, 1:41pm

Bác dùng uid của user làm seed đầu tiên cho hàm random, như vậy thì với mỗi user chỉ có một kết quả random duy nhất. OK chứ?

Ý tưởng là thế, còn bác làm cho nó phức tạp lên thì là việc của bác.
Nếu ngôn ngữ không có hàm random trên manual seed thì tự viết