هم‌زن لیست تصادفی - ابزار رایگان مخلوط کردن لیست آنلاین

فهرست‌به‌هم‌زن تصادفی چیست؟

فهرست‌به‌هم‌زن تصادفی ابزاری است که فهرستی از موارد را می‌گیرد و آن‌ها را با ترتیبی جدید و تصادفی بازمی‌چیند. نام‌ها، کارها یا هر چیز دیگری را هرکدام در یک خط وارد کنید تا ابزار آن‌ها را طوری جابه‌جا کند که همهٔ ترتیب‌های ممکن شانس برابری برای ظاهر شدن داشته باشند. این ابزار از به‌هم‌ریختن فیشر–ییتس، الگوریتمی شناخته‌شده برای تولید ترتیب‌های تصادفی بدون سوگیری، استفاده می‌کند.

چگونه از فهرست‌به‌هم‌زن تصادفی استفاده کنیم

1. فهرست را در کادر تایپ یا جای‌گذاری کنید؛ هر مورد در یک خط.
2. روی «تصادفی‌سازی فهرست» کلیک کنید. موارد فوراً بازچینش می‌شوند.
3. فهرست به‌هم‌ریخته را که زیر دکمه و با ترتیب جدید شماره‌گذاری شده است، بخوانید.
4. برای یک به‌هم‌ریزی مستقل و جدید، دوباره روی «تصادفی‌سازی فهرست» کلیک کنید.
5. برای کپی کردن ترتیب جدید روی «کپی نتیجه» کلیک کنید، یا برای شروع دوباره «پاک کردن» را بزنید.

خطوط خالی در ورودی به‌طور خودکار حذف می‌شوند؛ بنابراین شکست‌های خط اضافی در نتایج ورودی‌های خالی ایجاد نمی‌کنند.

الگوریتم به‌هم‌ریختن فیشر–ییتس چگونه کار می‌کند؟

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

فرمول به‌هم‌ریختن فیشر–ییتس

برای فهرستی شامل n مورد که جایگاه‌های آن از ۰ تا جایگاه n − ۱ شماره‌گذاری شده‌اند:

1for i from n − 1 down to 1:
2    choose a random whole number j, where 0 ≤ j ≤ i
3    swap the items at positions i and j
4

حلقه n − ۱ بار اجرا می‌شود، بنابراین به‌هم‌ریختن در مجموع تقریباً n گام زمان می‌برد. به این زمان خطی گفته می‌شود و آن را به‌صورت O(n) می‌نویسند. چون الگوریتم هر جایگاه را دقیقاً یک بار بررسی می‌کند و هر بار از مجموعه‌ای رو به کوچک‌شدن و دقیقاً تعریف‌شده از موارد انتخاب می‌کند، هرکدام از n! ترتیب ممکن (فاکتوریل n: n × (n − ۱) × ... × ۱)، شانس برابری برای حاصل شدن دارند.

مثال: به‌هم‌ریختن فهرستی چهارموردی

با چهار مورد در جایگاه‌های ۰ تا ۳ شروع می‌کنیم: سیب، موز، گیلاس، خرما.

• i = ۳: انتخاب تصادفی j = ۰ است. جایگاه‌های ۳ و ۰ را جابه‌جا کنید → خرما، موز، گیلاس، سیب
• i = ۲: انتخاب تصادفی j = ۲ است. جابه‌جا کردن یک جایگاه با خودش چیزی را تغییر نمی‌دهد → خرما، موز، گیلاس، سیب
• i = ۱: انتخاب تصادفی j = ۰ است. جایگاه‌های ۱ و ۰ را جابه‌جا کنید → موز، خرما، گیلاس، سیب

ترتیب نهایی: موز، خرما، گیلاس، سیب.

با چهار مورد، فاکتوریل ۴ برابر ۲۴ ترتیب ممکن وجود دارد. هرکدام، از جمله این ترتیب، در هر بار به‌هم‌ریختن شانس ۱ از 24 برای ظاهر شدن دارد.

چرا فقط جفت‌های تصادفی را جابه‌جا نکنیم؟

روشی که ساده‌تر به نظر می‌رسد — انتخاب دو جایگاه تصادفی و جابه‌جا کردن آن‌ها چند بار — تصادفی به نظر می‌رسد، اما چنین نیست. برخی برنامه‌های اولیهٔ به‌هم‌ریختن از دههٔ ۱۹۵۰ به این روش کار می‌کردند و بی‌سروصدا بعضی ترتیب‌ها را بر دیگر ترتیب‌ها ترجیح می‌دادند، هرچند هیچ اجرای منفردی مشکوک به نظر نمی‌رسید. به‌هم‌ریختن فیشر–ییتس از این مشکل جلوگیری می‌کند، زیرا هر مورد دقیقاً یک بار به جایگاهی منتقل می‌شود که از مجموعه‌ای دقیقاً رو به کوچک‌شدن از انتخاب‌ها تعیین شده است؛ همین باعث می‌شود همهٔ ترتیب‌های نهایی احتمال برابری داشته باشند.

به‌هم‌ریختن فیشر–ییتس از کجا آمده است؟

آماردانان، رونالد فیشر و فرانک ییتس، این روش را در ۱۹۳۸ در کتابی از جدول‌های آماری برای به‌هم‌زدن دستی ترتیب‌ها هنگام طراحی آزمایش‌ها توصیف کردند. در ۱۹۶۴، ریچارد دورستنفلد آن را برای رایانه‌ها سازگار کرد تا فهرست بدون نیاز به فهرست دومی برای پیگیری موارد باقی‌مانده، در همان محل بازترتیب شود. دونالد کانوث این نسخهٔ رایانه‌ای را در کتاب ۱۹۶۹ خود با عنوان هنر برنامه‌نویسی رایانه‌ای گنجاند؛ به همین دلیل گاهی به آن به‌هم‌ریختن کانوث نیز گفته می‌شود. مرورگرهای وب امروزه از همین الگوریتم استفاده می‌کنند.

کاربردهای رایج فهرست‌به‌هم‌زن

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

به‌هم‌ریختن ساده همیشه مناسب نیست. اگر بعضی موارد باید بیشتر از موارد دیگر ظاهر شوند، انتخاب وزن‌دار گزینهٔ مناسب‌تری است. اگر لازم است از حضور هر دسته اطمینان حاصل شود، نمونه‌گیری طبقه‌ای بهتر از یک به‌هم‌ریختن تصادفی منفرد عمل می‌کند.

پرسش‌های متداول

آیا این به‌هم‌ریختن واقعاً تصادفی است؟

این ابزار به مولد اعداد شبه‌تصادفی مرورگر وب (PRNG) متکی است؛ فرمولی که دنباله‌هایی از اعداد تولید می‌کند که برای کاربردهای عملی مانند تصادفی به نظر می‌رسند. این برای تعیین ترتیب کلاس، تعیین تیم‌های مسابقات یا انتخاب فیلم کافی است. این روش برای رمزنگاری، سامانه‌های قمار یا هر موردی که پول یا امنیت به غیرقابل‌پیش‌بینی بودن وابسته است طراحی نشده است؛ این موارد به مولدهای اعداد تصادفی تأییدشده نیاز دارند.

آیا ابزار فهرست من را به یک سرور می‌فرستد؟

خودِ به‌هم‌ریختن کاملاً در مرورگر و با استفاده از جاوااسکریپت اجرا می‌شود؛ بنابراین برای بازترتیب فهرست به درخواست شبکه نیازی نیست. فهرست فعلی همچنین در نشانی وب صفحه نوشته می‌شود، پس با بارگذاری مجدد یا نشانک‌گذاری، فهرست از بین نمی‌رود. اگر آن نشانی کپی، به‌اشتراک گذاشته یا دوباره باز شود، فهرست نیز همراه آن منتقل می‌شود، از جمله به هر سروری که بعداً آن صفحه را بارگذاری کند. اگر این موضوع اهمیت دارد، از قرار دادن اطلاعات حساس در فهرست خودداری کنید.

با موارد تکراری چه اتفاقی می‌افتد؟

موارد تکراری حفظ می‌شوند. اگر «سم» دو بار در ورودی ظاهر شود، در خروجی به‌هم‌ریخته نیز دو بار ظاهر خواهد شد، هرچند ممکن است در جایگاه‌های متفاوتی باشند.

آیا برای تعداد مواردی که می‌توانم به‌هم بریزم محدودیتی وجود دارد؟

هیچ محدودیتی در ابزار تعیین نشده است. چون به‌هم‌ریختن در زمان خطی اجرا می‌شود، حتی فهرست‌های طولانی نیز در هر دستگاه مدرن، در کسری از ثانیه بازترتیب می‌شوند.

به‌هم‌ریختن چه تفاوتی با مرتب‌سازی دارد؟

مرتب‌سازی موارد را بر اساس قاعده‌ای ثابت، مانند ترتیب الفبایی، می‌چیند و برای ورودی یکسان همیشه نتیجهٔ یکسانی تولید می‌کند. به‌هم‌ریختن موارد را به‌طور تصادفی می‌چیند و تقریباً هر بار ترتیب متفاوتی تولید می‌کند، حتی با ورودی کاملاً یکسان.

آیا می‌توانم یک فهرست را بیش از یک بار به‌هم بریزم؟

بله. هر بار کلیک روی «تصادفی‌سازی فهرست» الگوریتم را مستقل از هر به‌هم‌ریختن قبلی دوباره اجرا می‌کند. در فهرست‌های کوچک، تکرار یک ترتیب ممکن است به‌طور تصادفی رخ دهد؛ در فهرست‌های بزرگ، احتمال آن بسیار کم می‌شود.