Làm thế nào để tạo một hoán vị ngẫu nhiên của một mảng?

Question

Tôi đã viết hàm này trong C và tôi muốn nó tạo một hoán vị ngẫu nhiên hoặc một danh sách các số từ 1 đến n. Tôi gặp khó khăn khi nhận được nó để không có số lặp lại. Vì vậy, nếu bạn có n = 4, tôi muốn nó trả về một mảng ngẫu nhiên có chứa 1-4 mỗi một lần duy nhất, ví dụ: {1,3,4,2}

int* random(int n) 
{ 
    int* r = malloc(n * sizeof(int)); 
    // initial range of numbers 
    for(int i=0;i<n;++i){ 
     r[i]=i+1; 
    } 
    // shuffle 
    for (int i = 1; i <= n; ++i){ 
     int j = rand() % i; 
     r[i] = r[j]; 
     r[j] = i; 
    } 
    return r; 
} 

Answer 1

Thay đổi thứ hai for vòng lặp của bạn để :

for (int i = n-1; i >= 0; --i){ 
    //generate a random number [0, n-1] 
    int j = rand() % (i+1); 

    //swap the last element with element at random index 
    int temp = r[i]; 
    r[i] = r[j]; 
    r[j] = temp; 
} 

Đây là thuật toán xáo trộn Fisher-Yates. Tôi đã nghe nói sử dụng rand() % n không phân phối đồng đều, bạn đã được cảnh báo.

Và nếu bạn muốn tạo hoán vị duy nhất, bạn có thể lưu trữ các hoán vị được tạo, có thể trong Dictionary hoặc Hashmap và tra cứu mọi lúc bạn quay trở lại. Tôi không nghĩ rằng C có tích hợp sẵn nhưng phải có sẵn thư viện.

Answer 2

Đây có thể không phải là cách hiệu quả nhất, nhưng vì bạn đã nhập mảng ngay từ đầu, bạn có thể chỉ cần lặp qua các phần tử và cho từng phần tử, chọn một chỉ mục ngẫu nhiên trong phạm vi từ 1 đến n và hoán đổi với mặt hàng đó:

int* random(int n) 
{ 
    int* r = malloc(n * sizeof(int)); 
    for(int i=0;i<n;++i){ 
     r[i]=i+1; 
    } 
    for(int i=0; i<n; ++i){ 
     int randIdx = rand() % n; 
     // swap r[i] with r[randIdx] 
     int t = r[i]; 
     r[i] = r[randIdx]; 
     r[randIdx] = t; 
    } 
    return r; 
} 

Tôi không biết điều này có hiệu quả nhất hay thậm chí nếu nó phân phối tốt nhất. Nhưng nó khá đơn giản :-)