انتخاب گره تصادفی از لیست پیوندی – به زبان ساده

در این مطلب، روش انتخاب گره تصادفی از لیست پیوندی بیان شده است. یک لیست پیوندی داده شده و هدف انتخاب یک «گره» (Node) تصادفی از «لیست پیوندی» (Linked List) (احتمال انتخاب یک گره باید $$1/N$$ باشد) است. یک «مولد اعداد تصادفی» (Random Number Generator) نیز داده شده است. راهکار ساده زیر برای حل این مساله قابل استفاده است.

1. تعداد گره‌ها را با پیمایش لیست بشمار.
2. مجددا لیست را پیمایش و گره‌ای با احتمال $$1/N$$ را انتخاب کن. انتخاب را می‌توان با تولید یک عدد تصادفی از صفر تا N-i برای iاُمین گره انجام داد. همچنین، iاُمین گره تنها در صورتی انتخاب شود که عدد تولید شده برابر با صفر باشد (یا هر ثابت دیگری از صفر تا N-i).

با طرح‌های بالا، احتمال‌های یکنواخت حاصل می‌شود.

i = 1, probability of selecting first node = 1/N
i = 2, probability of selecting second node =
[probability that first node is not selected] * 
[probability that second node is selected]
= ((N-1)/N)* 1/(N-1)
= 1/N

به طور مشابه، احتمال انتخاب دیگر گره‌ها $$1/N$$ است. راهکار بالا نیازمند دو پیمایش لیست پیوندی است.

روش انتخاب یک گره تصادفی با تنها یک پیمایش

می‌توان از نمونه‌برداری «Reservoir» استفاده کرد. در ادامه، گام‌های لازم برای انتخاب تصادفی یک گره از لیست پیوندی با تنها یک پیمایش، بیان شده‌اند. این نسخه ساده‌تری از نمونه‌برداری Reservoir است؛ زیرا تنها نیاز به انتخاب یک کلید به جای k کلید دارد.

1. نتیجه را با اولین گره مقداردهی اولیه کن (result = head->key)
2. مقداردهی اولیه n = 2 را انجام بده.
3. اکنون، یکی یکی همه گره‌ها از دومین گره به بعد را در نظر بگیر.
   1. یک عدد تصادفی از صفر تا n-1 تولید کن. عدد تصادفی تولید شده را در j قرار بده.
   2. اگر j برابر با صفر است (می‌توان دیگر اعداد ثابت بین ۰ تا N-1 را انتخاب کرد)، نتیجه را با گره کنونی جایگزین کن.
   3. n = n+1
   4. current = current->next

در ادامه، پیاده‌سازی روش بالا در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «زبان سی» (C)، «جاوا» (Java) و «سی‌شارپ» (#C) انجام شده است.

انتخاب گره تصادفی از لیست پیوندی در ++C

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

انتخاب گره تصادفی از لیست پیوندی در C

انتخاب گره تصادفی از لیست پیوندی در جاوا

فیلم آموزش برنامه نویسی جاوا Java + گواهینامه در فرادرس

کلیک کنید

انتخاب گره تصادفی از لیست پیوندی در #C

خروجی قطعه کد بالا به صورت زیر است.

Before Deleting 
1 12 1 4 1 
After deleting 
12 1 4 1

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

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

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

^^