Làm thế nào để random 1 mảng a[] n phần tử từ 1 mảng b[] m phần tử có sẵn với số phần tử khá lớn mà không bị trùng lặp

C++ thì xài <random> ấy. random kiểu trên trùng là đương nhiên. Muốn các phần tử ko trùng nhau kiểu nào? n phần tử có giá trị 1,2,3,…,n hay là n phần tử có giá trị bất kì? Nếu là kiểu 1,2.3,…,n thì tạo 1 mảng chứa n giá trị rồi shuffle mảng đó là xong, còn n phần tử giá trị bất kì thì phải xài 1 cái set để loại phần tử trùng nhau, xài std::set<int> hoặc std::unordered_set<int>

“random dựa vào thời gian” nghĩa là sao @_@ Chỉ có seed là dựa vào thời gian thôi mà random bằng rand() đâu có liên quan gì tới thời gian. C++ ko có pseudo random bit generator nào “an toàn” cho mật mã hết (CSPRNG), nhưng xài MSVC 2017 thì có std::random_device được “nổ” là CSPRNG.

Nếu là kiểu 1,2.3,…,n thì tạo 1 mảng chứa n giá trị rồi shuffle mảng đó là xong

Cái này em có đọc bài của anh trên diễn đàn rồi. Nhưng kiểu em muốn là có 100 ảnh được đánh số từ 1->100. Cần chọn ra 20 ảnh chẳng hạn. 20 ảnh này được lấy ra từ 100 ảnh và 20 ảnh này không được trùng nhau
Vì số phần tử khá lớn, ví dụ 5000 ngìn ảnh, cần lấy ra 1500 ảnh mà random dựa vào hàm thời gian rồi viết 1 hàm kiểm tra sự trùng lặp thì hơi lâu

cách dễ nhất vẫn là shuffle hết 100 số đó rồi lấy 20 số đầu tiên trong mảng đã shuffle.

việc xáo trọn đó có ngẫu nhiên không anh

có chứ sao ko @_@

tạo 1 cái random engine, rồi đẩy nó vào std::shuffle trong <algorithm>

cách “khó” hơn 1 chút là xài reservoir sampling

template <typename PRNG>
std::vector<int> reservoirSampling(const std::vector<int>& S, size_t k, PRNG& prng)
{
    std::vector<int> R(begin(S), begin(S)+k);
    for (size_t i = k; i < S.size(); ++i)
    {
        size_t j = std::uniform_int_distribution<size_t>{0, i}(prng);
        if (j < k) R[j] = S[i];
    }
    return R;
}

E thây xóa trộn mảng vẫn dùng hàm rand dựa vào thời gian
Nhưng chắc mỗi lần lấy phần tử xong bỏ phần đó đi thì sẽ k trùng lặp được là ổn rồi

STDIO

Xáo Trộn Một Mảng Cho Trước :: Bài viết :: STDIO

Bài viết hướng dẫn độc giả, đặc biệt là những độc giả mới bắt đầu làm quen với lập trình hình thành tư duy phân tích và thiết kế một thuật toán xáo trộn 1 mảng cho trước.

bài trang này nó để srand(time(NULL)); ở trong cái hàm kia thì tác giả viết chưa đúng rồi ~.~

chưa kể cách xài srand sai, C++ hiện đại ko ai xài rand() nữa hết. Google "rand() Considered Harmful " là thấy.

ko có cái gọi là dùng hàm rand dựa vào thời gian, seed hàm rand dựa vào thời gian

tác giả bài đó chắc chưa nghe nói tới std::random_shuffle có sẵn trong <algorithm> nên mới khổ dâm viết 1 cái hàm shuffle mà viết cũng sai nữa ~.~ (để srand ở trong). Nhưng C++14 đã đánh dấu random_shuffle là lỗi thời rồi, và C++17 đã xóa sổ nó ra khỏi thư viện chuẩn vì ko ai khuyến khích xài rand() nữa cả. Sở dĩ nó còn là vì C++ phải chạy code C được.

http://en.cppreference.com/w/cpp/algorithm/sample

C++17 có sẵn hàm sample luôn nè, khỏi cần khổ dâm viết hàm riêng

Thuật toán viết bằng C#:

int[] DeBai(int[] b, int Size)
{
	var Input = new List<int>(b);
	var X = new Random();
	var a = new List<int>;
	for (int i = 0; i < Size; i += 1)
	{
		k = X.Next(1, Input.Count);
		a.Add(Input[k]);
		Input.RemoveAt(k);
	}
	return a.ToArray();
}

2 cách đơn giản này ổn không anh nhẩy

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]


-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

sao ko xài std::shuffle 1 dòng @_@, còn là sinh viên năm 1 hay sao mà ko dám xài hàm trong thư viện chuẩn

#include <iostream>
#include <algorithm>
#include <random>
#include <numeric>
#include <chrono>
using namespace std::chrono;

int main()
{
    auto seed = duration_cast<seconds>(system_clock::now().time_since_epoch()).count();
    std::mt19937 prbg{seed};

    std::vector<int> arr(5000);
    std::iota(begin(arr), end(arr), 1); //arr = [1, 5000]

    std::shuffle(begin(arr), end(arr), prbg); //shuffle xong. lấy a[0] tới a[1499] là được 1500 số ngẫu nhiên thuộc đoạn [1, 5000]

    //C++17 sample
    std::vector<int> sample;
    std::sample(begin(arr), end(arr), std::back_inserter(sample), 1500, prbg); //xong, sample chứa 1500 phần tử ngẫu nhiên chọn từ arr.
}

void shuffleArray(unsigned int *data, unsigned int size) {
    unsigned int position, a = 0, b = size - 1, temp;
    srand(time(NULL));
    for (unsigned int i = 0; i < size; i++) {
        do {
            position = a + rand()%(b-a+1);
        } while (position == i);

        temp = data[i];
        data[i] = data[position];
        data[position] = temp;
    }
}

Em làm như thế nàyy ổn không anh nhẩy. E đang rảnh rảnh nên xem có cách nào đơn giản code được hem

xóa cái srand. Mà thôi code xài rand ko thèm đọc @_@

Để em tìm hiểu xem tại sao không nên dùng rand. Giờ mới biết :3

dễ lắm, chạy code này trên VC++ là thấy @_@

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

bool randChance(int chance)
{
    return rand() % 10000 < chance;
}

int main()
{
    srand(time(0));
    int N = 1000000;
    int chance = 1500; // 15% chance
    int success = 0;
    for (int i = 0; i < N; ++i)
        success += randChance(chance);
    
    std::cout << std::fixed << std::setprecision(2) << success * 100.0 / N << "%\n";
}

nó in ra 18% chứ ko phải 15%

Nếu mảng b[] không hằng thì chỉ cần n thao tác Fisher-Yates trên b rồi copy phần đầu qua a[].
Nếu b là hằng thì phải chọn và thay thế, O(m).

Hai trường hợp đều là O(1) mem.