عدد غیر تکراری

[mhzarei76]

با سلام چگونه میتوانیم با تابع rand یک عدد تصادفی غیر تکراری ایجادکنیم;

[rahnema1]

سلام
مثلا می خواهید اعداد بین صفر تا ۹ را به صورت تصادفی و غیر تکراری انتخاب کنید روش را یج به این صورته که اعداد صفر تا ۹ را به صورت پشت سر هم در یک آرایه یا vector ذخیره کنید و سپس این آرایه را به شکل تصادفی به هم بریزید یا shuffle کنید
در کتابخانه استاندارد ++C ما تابع std::shuffle داریم که همین کار را انجام میده

[mohammad-i]

من هم همین سوال رو دارم؛


سلام
مثلا می خواهید اعداد بین صفر تا ۹ را به صورت تصادفی و غیر تکراری انتخاب کنید روش را یج به این صورته که اعداد صفر تا ۹ را به صورت پشت سر هم در یک آرایه یا vector ذخیره کنید و سپس این آرایه را به شکل تصادفی به هم بریزید یا shuffle کنید
در کتابخانه استاندارد ++C ما تابع std::shuffle داریم که همین کار را انجام میده
خب با این کار که نمیشه گفت عدد غیر تکراری نداریم.
فکر میکنم باید بعد از قرار دادن اعداد در ارایه، بازه تابع رندم رو آرایه قرار بدیم و بعد از هر بار انتخاب یک عدد از ارایه ، آن عدد حذف بشه.
مشکل من قرار دادن آرایه به عنوان بازه تابع رندم هست.

[pbm_soy]

یک عدد تصادفی بین یک تا ده را تولید کنید
عدد تصادفی تولید شده مورد نظر را در آرایه جستجو کنید اگر وجود نداشت در اولین خانه خالی آرایه ذخیره کن و سپس اندیس اشاره گر خانه خالی آرایه را یکی ببر جلو
اگر اندیس اشاره گر خانه خالی آرایه به انتهای آرایه رسیده باشد از حلقه خارج شود

این چند خط را داخل یک حلقه بینهایت قرار دهید والبته قبل از شروع حلقه مواردی را مشخص کنید

[mohammad-i]

با تشکر از پاسخ شما؛ ولی اگه طول ارایه زیاد باشه بار برنامه میره بالا.

اگر کد ما به این شکل باشد:



int[] list = { 1, 2, 3, 4, 5 };


Random rnd = new Random();
int l1 = rnd.Next(1, 5);


آیا امکانش هست به جای عدد 5 در rnd.next از محتوای ارایه استفاده کنیم؟(طول آرایه منظورم نیست)

[Ananas]

میتونید تعداد بیتهارو بیشتر کنید تا احتمال برخورد کم بشه. مثلا یک عدد 64 بیتی. که برای ساختش هم میتونید هر بایت رو یک بار با تابع rand پر کنید. این خودش میشه یک تابع. مثال:


#include <stdint.h>
#include <iostream>
#include <conio.h>
using namespace std;

int64_t Rand64()
{
int64_t i64 = rand();
i64 |= (int64_t)rand() << 16;
i64 |= (int64_t)rand() << 32;
i64 |= (int64_t)rand() << 48;
return i64;
};

void PrintI64(const int64_t i64)
{
char str[16];
int32_t i32 = (int32_t)(i64 >> 32);
std::cout << std::ultoa(i32, str, 16);
i32 = (int32_t)(i64 & 0x00000000ffffffffULL);
std::cout << std::ultoa(i32, str, 16);
};

int main()
{
for (int i = 0; i < 100; i++)
{
PrintI64(Rand64());
std::cout << std::endl;
};

getch();
return 0;
};

البته هیچ تضمینی نیست که تکراری نباشه ولی احتمالش ضعیف میشه. میتونید دوتا 64 بیتی رو بذارید کنار هم بشه 128 که دیگه خیلی احتمالش کمتر بشه. ولی کلا با این روش عدد بزرگ میشه.

[mohammad-i]

یعنی هیچ راهی نداره که اعداد انتخوابی در رندم از یک آرایه یا یک لیست انتخواب بشن؟

[Ananas]

یعنی هیچ راهی نداره که اعداد انتخوابی در رندم از یک آرایه یا یک لیست انتخواب بشن؟

چرا نداره؟! دوستان که گفتن چیکار کنید!
میتونید یک آرایه از اعداد رو بسازید و به ترتیب از صفر تا n و بعد جای اعداد رو با هم جابجا کنید. ینی به هم بزنید اعضای آرایه رو. بعد با اندیس از صفر تا n میتونید عدد رندم داشته باشید بدون تکرار.
و یا یک آرایه از اعداد رو بسازید و هر عضو رو یک عدد رندم مقدار بدید. و هر عضو رو قبل از مقدار دادن چک کنید اگر قبلا در آرایه بود یک بار دیگه اون رو بسازید. و میتونید برای استفاده از اندیس صفر شروع کنید تا آخرین عضو.
و یا اینکه از bitsset استفاده کنید. بعد هر بار که تابع رندم رو فراخونی میکنید، بیت معادل اون رو چک کنید که اگر صفر بود عدد رو برگردونه و بیت معادل رو هم علامت بزنه و یک کنه و اگر یک بود یک بار دیگه خودشو صدا بزنه. مثال:

#include <iostream>
#include <conio.h>
#include <bitset>
#include <stdint.h>
using namespace std;

template<size_t _Start, size_t _Count>
class TRandomClass
{
private:
int Get_Rand()
{
int ret = (int)(
( (int64_t)std::_lrand() * (int64_t)_Count ) / (int64_t)LRAND_MAX
);
if (this->Bits[ret])
{
if (__Counter >= _Count)
return 0x80000000L;
else
return Get_Rand();
}
else
{
__Counter++;
Bits[ret] = true;
return ret;
};
};
int __Counter;
std::bitset< _Count > Bits;
public:
TRandomClass()
{
__Counter = 0;
};
int GetRandom()
{
return Get_Rand() + _Start;
};
};

int main()
{
TRandomClass<5, 12> rand_5_to_17;
for (int i = 0; i < 15; i++)
std::cout << rand_5_to_17.GetRandom() << std::endl;
getch();
return 0;
};

این کلاس موقع ساخته شدن از شما شروع بازه ی اعداد رندم و تعداد رو میگیره. و یک تابع داره که با استفاده از اون میتونید اعداد رندم غیر تکراری بگیرید تو همون بازه. اگر از این کلاس تعداد بیشتر عدد رندم درخواست کنید مقدار 0x80000000L رو برمیگردونه.