مجموعه (نوع داده انتزاعی)
چند مجموعه

چندمجوعه یا خورجین یک تعمیم مفهوم مجموعه است. تفاوت آن با مجموعه این است که اجازه می دهد تا مقادیر مساوی و تکراری داشته باشیم. این است که در دو معنای متمایز استفاده می شود: ارزش هم برابر هستند یکسان در نظر گرفته، و به سادگی شمارش، و یا مقادیر برابر باشند معادل در نظر گرفته، و به عنوان کالای مجزا ذخیره می شود. به عنوان مثال ، با توجه به لیستی از افراد (با نام) و سن (در سال) ، می توان چندین گروه از سنین را ایجاد کرد که به سادگی تعداد افراد در یک سن مشخص را محاسبه می کند. متناوباً ، می توان افراد زیادی را ساخت ، جایی که دو نفر در صورتی که سن آنها یکسان باشد معادل در نظر گرفته می شوند (اما ممکن است افراد مختلف باشند و نام های مختلفی داشته باشند) ، در این صورت هر جفت (نام ، سن) باید ذخیره شود و انتخاب در یک سن معین به همه افراد در یک سن داده می شود.
به طور رسمی ، این امکان وجود دارد که اشیا in در علوم کامپیوتر تحت برخی معادلات هم ارزی "برابر" قلمداد شوند اما در رابطه دیگری هنوز مشخص باشند. برخی از انواع پیاده سازی چند مجموعه ، اشیا equal مساوی مجزا را به عنوان موارد جداگانه در ساختار داده ذخیره می کنند. در حالی که دیگران آن را به یک نسخه تقسیم می کنند (نسخه اول با آن مواجه می شوند) و تعداد عددی مثبت را از کثرت عنصر حفظ می کنند.
همانند مجموعه ها ، چند مجموعه به طور طبیعی می توانند با استفاده از جدول هش یا درختان ، که دارای عملکردهای مختلف هستند ، اجرا شوند.
مجموعه همه کیسه ها در بالای نوع T با عبارت T ارائه می شود. اگر توسط چند مجموعه یکی موارد مساوی را یکسان در نظر گرفته و به سادگی آنها را بشمارد ، پس می توان چند مجموعه را به عنوان تابعی از دامنه ورودی به اعداد صحیح غیر منفی تفسیر کرد ( طبیعی اعداد ) ، شناسایی یک مجموعه با عملکرد نشانگر آن را تعمیم می دهد. در بعضی موارد ، یک مجموعه چندگانه به این معنی شمارش ممکن است تعمیم داده شود تا مقادیر منفی مانند پایتون مجاز باشد.
کتابخانه الگوی استاندارد C ++ چندین مجموعه مرتب شده و مرتب نشده را پیاده سازی می کند. این فراهم می کند multiset کلاس برای MultiSet به مرتب شده اند، به عنوان یک نوع ظرف انجمنی ، که پیاده سازی این MultiSet به استفاده از یک درخت جستجوی دودویی خود متوازن . unordered_multiset برای چند مجموعه مرتب نشده ، به عنوان نوعی کانتینر انجمنی غیر مرتب ، فراهم می کند که این چند مجموعه را با استفاده از جدول هش پیاده سازی می کند. چند مجموعه مرتب نشده از C ++ 11 استاندارد است. قبلاً STL SGI hash_multiset که کپی و در نهایت استاندارد شده ارائه می دهد.
برای جاوا ، کتابخانه های شخص ثالث قابلیت چند مجموعه ای را ارائه می دهند:
مجموعه های Apache Commons Bag و SortedBag را با کلاس های اجرایی مانند HashBag و TreeBag فراهم می کند.
Google Guava با کلاسهای پیاده سازی مانند HashMultiset و TreeMultiset Multiset را فراهم می کند.
اپل فراهم می کند NSCountedSet کلاس به عنوان بخشی از کاکائو و CFBag و CFMutableBag انواع به عنوان بخشی از CoreFoundation .
کتابخانه استاندارد پایتون collections. Counter ، که شبیه به چند مجموعه است.
Smalltalk شامل Bag ، که می تواند نمونه ای از آن باشد که از هویت یا برابری به عنوان محمول برای آزمون ورود استفاده کند.
در مواردی که ساختار داده ای چند مجموعه ای در دسترس نباشد ، استفاده از یک مجموعه منظم برای رفع اشکال است ، اما عدد مساوی موارد آن را نادیده بگیرید تا همیشه "مساوی" بر روی اشیا objects مجزا برگردد (با این حال ، چنین مواردی هنوز قادر به ذخیره چندین مورد نیستند از همان شی object استفاده کنید) یا از یک آرایه انجمنی استفاده کنید که مقادیر را بر ضرب های عدد صحیح آنها ترسیم کند (این به هیچ وجه نمی‌تواند بین عناصر مساوی تفاوت قائل شود).
عملیات معمول روی کیسه ها:
contains( B, x ) : بررسی می کند که آیا عنصر x (حداقل یک بار) در کیسه B وجود دارد
is_sub_bag( B 1, B 2 ) : بررسی می کند که آیا هر عنصر در کیسه B 1 در B 1 رخ می دهد بیش از آنچه در کیسه B 2 وجود دارد . گاهی اوقات به عنوان B 1 ⊑ B 2 نشان داده می شود.
count( B, x ) : تعداد دفعاتی که عنصر x در کیسه B رخ می دهد را برمی گرداند. گاهی اوقات به عنوان B # x نشان داده می شود.
scaled_by( B, n ) : به یک عدد طبیعی n داده می شود ، کیسه ای برگردانده می شود که شامل همان عناصر کیسه B است ، با این تفاوت که هر عنصری که m بار در B اتفاق می افتد n * m بار در کیسه حاصل می شود گاهی اوقات به عنوان n ⊗ B نشان داده می شود.
union( B 1, B 2 ) : کیسه ای را شامل می کند که فقط شامل مقادیری باشد که در کیسه B 1 یا کیسه B 2 وجود دارد ، با این تفاوت که تعداد دفعاتی که مقدار x در کیسه حاصله اتفاق می افتد برابر است با ( B 1 # x) + ( B 2 # x) ؛ گاهی اوقات به عنوان B 1 ⊎ B 2 نشان داده می شود.