Tạo dãy số ngẫu nhiên không trùng trong C/C++ có code minh họa

Làm sao để tạo dãy số ngẫu nhiên không trùng nhau trong C/C++? Hãy cùng Nguyễn Văn Hiếu đi giải quyết bài toán sinh số ngẫu nhiên không trùng trong bài viết này nhé. Mình sẽ hướng dẫn các bạn hai cách khác nhau để tạo dãy số ngẫu nhiên không trùng lặp. Bắt đầu nào…

NỘI DUNG BÀI VIẾT

1. Tạo dãy số ngẫu nhiên không trùng

Nếu bạn chưa đọc bài viết hướng dẫn tạo số ngẫu nhiên, bạn có thể đọc trước để hiểu về hàm tạo số ngẫu nhiên trong bài viết này.

Bài này mình sẽ không giải thích chi tiết cách hàm tạo số ngẫu nhiên hoạt động. Mình sẽ tập trung giải thích cách để tạo các số ngẫu nhiên không trùng lặp.

Bài toán 1: Hãy in ra 10 số nguyên ngẫu nhiên khác nhau trong đoạn [1, 100]

Bài toán 2: Hãy xáo trộn vị trí các phần tử trong mảng số nguyên có n phần tử. Hiểu cụ thể hơn chính là xáo trộn dãy chỉ số từ [0, n-1] .

Mình sẽ hướng dẫn các bạn 2 cách khác nhau, hãy cùng đi vào cụ thể từng cách nào.

2. Tạo dãy số ngẫu nhiên khác nhau sử dụng map

Đây là một cách trâu bò, ý tưởng của chúng ta là sinh số ngẫu nhiên, kiểm tra nó đã có hay chưa? Nếu chưa có thì mới lấy. Như vậy, cuối cùng ta sẽ thu được dãy số có các giá trị khác nhau.

Cấu trúc dữ liệu map cho chúng ta thực hiện kiểm tra với độ phức tạp là O(1). Điều này giúp code chúng ta chạy nhanh hơn.

Lưu ý: Số lượng số cần random phải >= số lượng số có thể random. Do vậy, mình cần check như sau:

do{
    cout << "\nNhap so luong so can random = ";
    cin >> cnt;
}while(cnt > maxN - minN + 1);

do{

cout << "\nNhap so luong so can random = ";

cin >> cnt;

}while(cnt > maxN - minN + 1);

Nếu vi phạm, code sẽ bị lặp vô tận vì không tìm được số thỏa mãn.

#include <iostream>
using namespace std;
#include <stdlib.h>
#include <map>
#include <time.h>

int main(){
    srand((int)time(0));
    int r, minN, maxN;
    cout << "\nNhap minN = ";
    cin >> minN;
    cout << "\nNhap maxN = ";
    cin >> maxN;
    int cnt;
    do{
        cout << "\nNhap so luong so can random = ";
        cin >> cnt;
    }while(cnt > maxN - minN + 1);
    
    map<int, bool> vis;
    
    for(int i = 0; i < cnt; ++i){
        // Random cho toi khi r chua co trong map vis
        do{
            r = minN + rand() % (maxN + 1 - minN);
        }while(vis.find(r) != vis.end());
        printf("%d ",r);
        // Danh dau r da co.
        vis[r] = true;
    }    
}

#include <iostream>

using namespace std;

#include <stdlib.h>

#include <map>

#include <time.h>

int main(){

srand((int)time(0));

int r, minN, maxN;

cout << "\nNhap minN = ";

cin >> minN;

cout << "\nNhap maxN = ";

cin >> maxN;

int cnt;

do{

cout << "\nNhap so luong so can random = ";

cin >> cnt;

}while(cnt > maxN - minN + 1);

map<int, bool> vis;

for(int i = 0; i < cnt; ++i){

// Random cho toi khi r chua co trong map vis

do{

r = minN + rand() % (maxN + 1 - minN);

}while(vis.find(r) != vis.end());

printf("%d ",r);

// Danh dau r da co.

vis[r] = true;

}

Kết quả chạy thử:

Nhap minN = 1

Nhap maxN = 20

Nhap so luong so can random = 20
13 19 20 7 15 12 16 10 8 9 3 6 18 2 14 1 17 4 11 5

Nhap minN = 1

Nhap maxN = 20

Nhap so luong so can random = 20

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

Trong trường hợp số lượng số cần random ít hơn số lượng giá trị có thể random thì đây là cách tốt nhất mà mình biết. Tất nhiên, trong trường bằng nhau như mình chạy thử phía trên thì cũng không quá lâu đâu. Nhiều trường hợp vẫn nhanh hơn cách thứ 2 đấy.

Tuy nhiên, đây không thực sự là cách tối ưu vì có thể phải chờ rất lâu mới có được những kết quả random cuối cùng. Các bạn hãy thử dùng cách 2 và so sánh giúp mình nhé.

3. Tạo dãy số ngẫu nhiên không trùng với mảng

Thư viện algorithm trong C/C++ có một hàm giúp chúng ta xáo trộn các phần tử của mảng. Đó chính là hàm random_shuffle():

template <class RandomAccessIterator>
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last);

1 2	template <class RandomAccessIterator> void random_shuffle (RandomAccessIterator first, RandomAccessIterator last);

Để dễ hình dung, chúng ta sẽ đi ngay vào ví dụ cụ thể nhé.

Giả sử bạn cần sinh 50 số ngẫu nhiên có giá trị trong phạm vi [100, 1000000]. Bạn hãy tạo cho mình một mảng đủ để chứa 1000000 - 100 + 1 phần tử(100, 101, 102, …. 1000000). Chúng ta có thể làm như sau:

for(int i = 100; i <= 1000000; ++i){
    arr[i-100] = i;
}

for(int i = 100; i <= 1000000; ++i){

arr[i-100] = i;

}

Tiếp đến, ta cần xáo trộn mảng này. Sau đó, việc của bạn rất đơn giản, lấy 500 phần tử đầu tiên của mảng.

Code hoàn chỉnh của tất cả các bước như sau:

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

const int MAX = 1e6 + 5;

int arr[MAX];

int main(){
    int minN = 100;
    int maxN = 1e6;
    // Ban co the su dung vector thay mang
    int N = maxN - minN + 1;
	// vector<int> v;
    for(int i = minN; i <= maxN; ++i){
    	arr[i - minN] = i;
//    	v.push_back(i);
	}
	random_shuffle(arr, arr + N);
//	random_shuffle(v.begin(), v.end());
	
	int take = 50;
	for(int i = 0; i < take; ++i){
		cout << arr[i] << " ";
//		cout << v[i] << " ";
	}
}

#include <iostream>

using namespace std;

#include <algorithm>

//#include <vector>

const int MAX = 1e6 + 5;

int arr[MAX];

int main(){

int minN = 100;

int maxN = 1e6;

// Ban co the su dung vector thay mang

int N = maxN - minN + 1;

// vector<int> v;

for(int i = minN; i <= maxN; ++i){

arr[i - minN] = i;

// v.push_back(i);

}

random_shuffle(arr, arr + N);

// random_shuffle(v.begin(), v.end());

int take = 50;

for(int i = 0; i < take; ++i){

cout << arr[i] << " ";

// cout << v[i] << " ";

}

Kết quả chạy thử:

971590 914909 991019 974934 922298 976089 971978 966587 988020 967409 995662 997653 981255 991586 999593 985141 961812 983475 964175 988346 983152 986791 972452 991595 979178 976575 919476 997491 975020 975770 972735 985023 975863 942484 920007 969245 996352 996894 977498 973845 989859 992467 969192 986331 978302 971142 996604 956965 959924 965380
--------------------------------
Process exited after 0.4305 seconds with return value 0
Press any key to continue . . .

971590 914909 991019 974934 922298 976089 971978 966587 988020 967409 995662 997653 981255 991586 999593 985141 961812 983475 964175 988346 983152 986791 972452 991595 979178 976575 919476 997491 975020 975770 972735 985023 975863 942484 920007 969245 996352 996894 977498 973845 989859 992467 969192 986331 978302 971142 996604 956965 959924 965380

--------------------------------

Process exited after 0.4305 seconds with return value 0

Press any key to continue . . .

Mình chạy thử với code trên và số liệu như trên thì thấy chậm hơn nhiều so với cách số 1. Có vẻ là cách số 1 vẫn sẽ vô đối nếu như số lượng số cần random là nhỏ hơn nhiều so với số giá trị có thể random. Có lẽ thuật toán shuffle ~ 1 triệu phần tử mất nhiều thời gian.

Kết luận

Mình nhờ các bạn đánh giá độ phức tạp của hai giải thuật này. Hoặc nếu các bạn có cách làm khác, hãy để lại trong phần bình luận để mọi người cùng trao đổi.

Mình cũng tin rằng sau khi đọc hết bài chia sẻ này, các bạn đã có thể tự giải quyết hai bài toán mình đặt ra ở phần đầu. Do đó, mình sẽ không giải 2 bài tập đó nữa 😀

Hi vọng bài chia sẻ đã giúp các bạn có thể tạo dãy số ngẫu nhiên không trùng lặp sử dụng C/C++. Chúc các học tập tốt!