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

مطالب مجله فرادرس را در جستجوی گوگل سریعتر ببینید
- تعداد گرهها را با پیمایش لیست بشمار.
- مجددا لیست را پیمایش و گرهای با احتمال را انتخاب کن. انتخاب را میتوان با تولید یک عدد تصادفی از صفر تا 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
به طور مشابه، احتمال انتخاب دیگر گرهها است. راهکار بالا نیازمند دو پیمایش لیست پیوندی است.
روش انتخاب یک گره تصادفی با تنها یک پیمایش
میتوان از نمونهبرداری «Reservoir» استفاده کرد. در ادامه، گامهای لازم برای انتخاب تصادفی یک گره از لیست پیوندی با تنها یک پیمایش، بیان شدهاند. این نسخه سادهتری از نمونهبرداری Reservoir است؛ زیرا تنها نیاز به انتخاب یک کلید به جای k کلید دارد.
- نتیجه را با اولین گره مقداردهی اولیه کن (result = head->key)
- مقداردهی اولیه n = 2 را انجام بده.
- اکنون، یکی یکی همه گرهها از دومین گره به بعد را در نظر بگیر.
- یک عدد تصادفی از صفر تا n-1 تولید کن. عدد تصادفی تولید شده را در j قرار بده.
- اگر j برابر با صفر است (میتوان دیگر اعداد ثابت بین ۰ تا N-1 را انتخاب کرد)، نتیجه را با گره کنونی جایگزین کن.
- n = n+1
- current = current->next
انتخاب گره تصادفی از لیست پیوندی در ++C
انتخاب گره تصادفی از لیست پیوندی در C
انتخاب گره تصادفی از لیست پیوندی در جاوا
انتخاب گره تصادفی از لیست پیوندی در #C
خروجی قطعه کد بالا به صورت زیر است.
Before Deleting 1 12 1 4 1 After deleting 12 1 4 1
این راهکار در صورتی که گره حذف شده آخرین گره در لیست باشد، کار نمیکند. برای اینکه راه حل کار کند، میتوان گره پایانی را به عنوان گره مجازی علامتگذاری کرد. در این صورت، برنامهها/تابعهایی که از این تابع استفاده میکنند نیز باید ویرایش شوند.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان دادهها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگآمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
^^
مطالب مجله فرادرس را در جستجوی گوگل سریعتر ببینید













