در این مطلب چگونگی نوشتن برنامه تولید عدد تصادفی با توزیع دلخواه مورد بررسی قرار خواهد گرفت. n عدد داده شده است که هر یک تعداد وقوع خاصی دارند. هدف، بازگرداندن (به عنوان خروجی) یک عدد تصادفی با احتمالی متناسب با تعداد وقوع آن عدد در مجموعه داده است. مثال زیر در این راستا قابل توجه است؛ فرض می‌شود که آرایه زیر، مجموعه اعداد داده شده است.

arr[] = {10, 30, 20, 40}

مجموعه داده زیر نیز تعداد تکرار هر یک از ارقام مجموعه داده را مشخص می‌کند.

freq[] = {1, 6, 2, 1}

خروجی باید به صورت زیر باشد.

۱۰ with probability 1/10
۳۰ with probability 6/10
۲۰ with probability 2/10
۴۰ with probability 1/10

کاملا واضح است که تولید کننده عدد تصادفی ساده، در اینجا به خوبی کار نخواهد کرد، زیرا تعداد تکرار وقوع هر عدد را برای تعیین احتمال انتخاب آن عدد، در نظر نمی‌گیرد. اکنون، نیاز به تبدیل مسئله به مسئله قابل حل‌تری است. یک راهکار ساده آن است که یک آرایه کمکی (فرض می‌شود []ux) گرفته شود و اعداد مطابق با تعداد تکرار آن‌ها در آرایه تکرار شوند. سپس، یک عدد تصادفی از بین عدد (r) بین ۰ و Sum-1 (شامل هر دو) تولید شود که در آن، Sum نشانگر مجموع تکرار آرایه (در مثال بالا، []freq) است. عدد تصادفی [aux[r در خروجی بازگردانده می‌شود.

محدودیت روش بیان شده در بالا، مصرف زیاد حافظه به ویژه در مواردی است که تعداد تکرار بسیار بالا باشد. اگر ورودی‌ها {۹۹۷ ,۸۷۶۱ ,۱} باشند، این روش قطعا ناکارآمد خواهد بود. اما پرسشی که در این وهله مطرح می‌شود آن است که چطور می‌توان مصرف حافظه را کاهش داد. در ادامه، الگوریتمی ارائه شده است که از (O(n فضای اضافی استفاده می‌کند که در آن، n تعداد عناصر موجود در آرایه ورودی است. الگوریتم مذکور در ادامه آمده است.

1. در نظر گرفتن یک آرایه کمکی (مثلا []prefix) با اندازه n.
2. جمع کردن این آرایه با prefix sum، به طوری که [prefix[i نشان دهنده مجموع اعداد از ۰ تا i است.
3. تولید عدد تصادفی (مثلا  بین ۱ تا r) Sum (شامل هر دو)، که در آن Sum نشان‌گر مجموع آرایه تکرار ورودی است.
4. پیدا کردن اندیس Ceil از عدد تصادفی تولید شده در گام ۳# در آرایه prefix. فرض می‌شود که اندیس indexc باشد.
5. بازگرداندن عدد تصادفی [arr[indexc که در آن، []arr حاوی n عدد ورودی است.

پیش از پیاده‌سازی رویکرد بالا، الگوریتم به طور کلی و همراه با یک مثال بررسی می‌شود. فرض می‌شود آرایه، تعداد تکرار و Prefix به صورت زیر هستند.

arr[]: {10, 20, 30}
freq[]: {2, 3, 1}
Prefix[]: {2, 5, 6}

با توجه به آنکه آخرین ورودی در prefix عدد ۶ است، همه مقادیر ممکن r به صورت [۱, ۲, ۳, ۴, ۵, ۶] هستند. خروجی به صورت زیر خواهد بود.

۱: Ceil is 2. Random number generated is 10.
۲: Ceil is 2. Random number generated is 10.
۳: Ceil is 5. Random number generated is 20.
۴: Ceil is 5. Random number generated is 20.
۵: Ceil is 5. Random number generated is 20.
۶٫ Ceil is 6. Random number generated is 30.

در مثال بالا، ۱۰ با احتمال دتو شیم (۲/۶)، ۲۰ با احتمال سه شیشم (۳/۶) و ۳۰ با احتمال یک شیشم (۱/۶) تولید شده است. هد عددی که [input[i تولید کرده است بر اساس تعداد تکرار آن است. زیرا شمارش اعداد صحیح در رنج [input[i است. مثلا در مثال بالا، ۳ سه بار تولید شده است، زیرا ۳ عدد صحیح ۳، ۴ و ۵ وجود دارد که ceil آن‌ها ۵ است.

برنامه تولید عدد تصادفی با توزیع دلخواه در ++C

// C++ program to generate random numbers 
// according to given frequency distribution  
#include <bits/stdc++.h> 
using namespace std; 
  
// Utility function to find ceiling of r in arr[l..h]  
int findCeil(int arr[], int r, int l, int h)  
{  
    int mid;  
    while (l < h)  
    {  
        mid = l + ((h - l) >> 1); // Same as mid = (l+h)/2  
        (r > arr[mid]) ? (l = mid + 1) : (h = mid);  
    }  
    return (arr[l] >= r) ? l : -1;  
}  
  
// The main function that returns a random number 
// from arr[] according to distribution array  
// defined by freq[]. n is size of arrays.  
int myRand(int arr[], int freq[], int n)  
{  
    // Create and fill prefix array  
    int prefix[n], i;  
    prefix[0] = freq[0];  
    for (i = 1; i < n; ++i)  
        prefix[i] = prefix[i - 1] + freq[i];  
  
    // prefix[n-1] is sum of all frequencies. 
    // Generate a random number with  
    // value from 1 to this sum  
    int r = (rand() % prefix[n - 1]) + 1;  
  
    // Find index of ceiling of r in prefix arrat  
    int indexc = findCeil(prefix, r, 0, n - 1);  
    return arr[indexc];  
}  
  
// Driver code  
int main()  
{  
    int arr[] = {1, 2, 3, 4};  
    int freq[] = {10, 5, 20, 100};  
    int i, n = sizeof(arr) / sizeof(arr[0]);  
  
    // Use a different seed value for every run.  
    srand(time(NULL));  
  
    // Let us generate 10 random numbers accroding to  
    // given distribution  
    for (i = 0; i < 5; i++)  
    cout << myRand(arr, freq, n) << endl;  
  
    return 0;  
}  
  
// This is code is contributed by rathbhupendra

برنامه تولید عدد تصادفی با توزیع دلخواه در C

//C program to generate random numbers according to given frequency distribution 
#include <stdio.h> 
#include <stdlib.h> 
  
// Utility function to find ceiling of r in arr[l..h] 
int findCeil(int arr[], int r, int l, int h) 
{ 
    int mid; 
    while (l < h) 
    { 
         mid = l + ((h - l) >> 1);  // Same as mid = (l+h)/2 
        (r > arr[mid]) ? (l = mid + 1) : (h = mid); 
    } 
    return (arr[l] >= r) ? l : -1; 
} 
  
// The main function that returns a random number from arr[] according to 
// distribution array defined by freq[]. n is size of arrays. 
int myRand(int arr[], int freq[], int n) 
{ 
    // Create and fill prefix array 
    int prefix[n], i; 
    prefix[0] = freq[0]; 
    for (i = 1; i < n; ++i) 
        prefix[i] = prefix[i - 1] + freq[i]; 
  
    // prefix[n-1] is sum of all frequencies. Generate a random number 
    // with value from 1 to this sum 
    int r = (rand() % prefix[n - 1]) + 1; 
  
    // Find index of ceiling of r in prefix arrat 
    int indexc = findCeil(prefix, r, 0, n - 1); 
    return arr[indexc]; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[]  = {1, 2, 3, 4}; 
    int freq[] = {10, 5, 20, 100}; 
    int i, n = sizeof(arr) / sizeof(arr[0]); 
  
    // Use a different seed value for every run. 
    srand(time(NULL)); 
  
    // Let us generate 10 random numbers accroding to 
    // given distribution 
    for (i = 0; i < 5; i++) 
      printf("%d\n", myRand(arr, freq, n)); 
  
    return 0;

برنامه تولید عدد تصادفی با توزیع دلخواه در جاوا

// Java program to generate random numbers 
// according to given frequency distribution  
class GFG 
{ 
  
// Utility function to find ceiling of r in arr[l..h]  
static int findCeil(int arr[], int r, int l, int h)  
{  
    int mid;  
    while (l < h)  
    {  
        mid = l + ((h - l) >> 1); // Same as mid = (l+h)/2  
        if(r > arr[mid])  
            l = mid + 1; 
        else
            h = mid;  
    }  
    return (arr[l] >= r) ? l : -1;  
}  
  
// The main function that returns a random number 
// from arr[] according to distribution array  
// defined by freq[]. n is size of arrays.  
static int myRand(int arr[], int freq[], int n)  
{  
    // Create and fill prefix array  
    int prefix[] = new int[n], i;  
    prefix[0] = freq[0];  
    for (i = 1; i < n; ++i)  
        prefix[i] = prefix[i - 1] + freq[i];  
  
    // prefix[n-1] is sum of all frequencies. 
    // Generate a random number with  
    // value from 1 to this sum  
    int r = ((int)(Math.random()*(323567)) % prefix[n - 1]) + 1;  
  
    // Find index of ceiling of r in prefix arrat  
    int indexc = findCeil(prefix, r, 0, n - 1);  
    return arr[indexc];  
}  
  
// Driver code  
public static void main(String args[]) 
{  
    int arr[] = {1, 2, 3, 4};  
    int freq[] = {10, 5, 20, 100};  
    int i, n = arr.length;  
  
    // Let us generate 10 random numbers accroding to  
    // given distribution  
    for (i = 0; i < 5; i++)  
    System.out.println( myRand(arr, freq, n) );  
}  
} 
  
// This code is contributed by Arnab Kundu

خروجی قطعه کدهای بالا به صورت زیر است. البه، خروجی با توجه به تصادفی بودن آن، ممکن است در اجراهای مختلف متفاوت باشد.

۴
۳
۴
۴
۴

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• معرفی منابع آموزش ویدئویی هوش مصنوعی به زبان فارسی و انگلیسی
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس

منبع [+]