सेट (अमूर्त डेटा प्रकार): Difference between revisions

Revision as of 15:33, 18 May 2023

भारत कंप्यूटर विज्ञान, उपसमुच्चय सार डेटा प्रकार है जो बिना किसी विशेष क्रम के अद्वितीय मूल्यों को संग्रहीत कर सकता है। यह परिमित समुच्चय की गणित अवधारणा का कंप्यूटर कार्यान्वयन है। अधिकांश अन्य संग्रह (सार डेटा प्रकार) प्रकारों के विपरीत, उपसमुच्चय से विशिष्ट तत्व को पुनः प्राप्त करने के अतिरिक्त, सामान्यतः उपसमुच्चय में सदस्यता के लिए मूल्य का परीक्षण किया जाता है।

कुछ उपसमुच्चय डेटा संरचनाएं स्थिर या एकत्रित उपसमुच्चय के लिए चित्रित किए गए हैं जो उनके निर्माण के पश्चात परिवर्तित नहीं होते हैं। स्थिर उपसमुच्चय स्वयं तत्वों पर केवल क्वेरी संचालन की अनुमति देते हैं - जैसे कि यह देखना कि क्या दिया गया मान उपसमुच्चय में है, या कुछ मनमाना क्रम में मानों की गणना करना अन्य वेरिएंट, जिन्हें डायनेमिक या म्यूतालिका उपसमुच्चय कहा जाता है, उपसमुच्चय से तत्वों को सम्मिलित करने एवं विस्थापित करने की भी अनुमति देते हैं।

बहुसमुच्चय विशेष प्रकार का उपसमुच्चय है, जिसमें तत्व उपसमुच्चय में कई बार दिखाई दे सकता है।

प्रकार सिद्धांत

प्रकार सिद्धांत में, उपसमुच्चय सामान्यतः उनके संकेतक फ़ंक्शन (विशेषता समारोह) के साथ पहचाने जाते हैं: तदनुसार, $A$ प्रकार के मूल्यों का उपसमुच्चय $2^{A}$ या ${\mathcal {P}}(A)$ द्वारा दर्शाया जा सकता है। (उपप्रकार एवं उपसमुच्चय को शोधन प्रकार द्वारा प्रतिरूपित किया जा सकता है, एवं भागफल उपसमुच्चय को परिवर्तनीय उपसमुच्चय द्वारा प्रतिस्थापित किया जा सकता है।) विशेषता कार्य $F$ उपसमुच्चय को $S$ परिभाषित किया जाता है।

F(x)={\begin{cases}1,&{\mbox{if }}x\in S\\0,&{\mbox{if }}x\not \in S\end{cases}}

सिद्धांत रूप में, कई अन्य अमूर्त डेटा संरचनाओं को मानक संचालन पर लगाए गए अतिरिक्त संचालन एवंअतिरिक्त सिद्धांतों के साथ उपसमुच्चय संरचनाओं के रूप में देखा जा सकता है। उदाहरण के लिए, अमूर्त हीप डेटा संरचना को उपसमुच्चय संरचना के रूप में देखा जा सकता है min(S) संचालन जो सबसे अल्प मूल्य का तत्व लौटाता है।

संचालन

कोर उपसमुच्चय-सैद्धांतिक संचालन

कोई उपसमुच्चय के बीजगणित के संचालन को परिभाषित कर सकता है:

union(S,T): समुच्चय S एवं T का संघ (उपसमुच्चय सिद्धांत) लौटाता है।
intersection(S,T): समुच्चय S एवं T का प्रतिच्छेदन (उपसमुच्चय सिद्धांत) लौटाता है।
difference(S,T): समुच्चय S एवं T का अंतर (उपसमुच्चय सिद्धांत) लौटाता है।
subset(S,T): विधेय जो परीक्षण करता है कि क्या समुच्चय S, समुच्चय T का उपसमुच्चय है।

स्थैतिक उपसमुच्चय

स्थैतिक उपसमुच्चय स्थिर S द्वारा प्रदान किए जा सकने वाले विशिष्ट संचालन हैं:

is_element_of(x,S): परिक्षण किया जाता है कि क्या मान x उपसमुच्चय S में है।
is_empty(S): परिक्षण किया जाता है कि उपसमुच्चय S रिक्त है या नहीं।
size(S) या cardinality(S): एस में तत्वों की संख्या लौटाता है।
iterate(S): ऐसा फ़ंक्शन लौटाता है जो प्रत्येक आह्वान पर S का एवं कुछ मनमाना क्रम में मान देता है।
enumerate(S): कुछ मनमानी क्रम में S के तत्वों वाली सूची देता है।
build(x₁,x₂,…,x_n,): मान x के साथ x₁,x₂,...,x_n उपसमुच्चय संरचना बनाता है।
create_from(collection): दिए गए संग्रह के सभी तत्वों (सार डेटा प्रकार) या दिए गए पुनरावर्तक द्वारा लौटाए गए सभी तत्वों वाली नई उपसमुच्चय संरचना बनाता है।

गतिशील उपसमुच्चय

गतिशील उपसमुच्चय संरचनाएं सामान्यतः जोड़ती हैं,

create(): प्रारंभ में रिक्त उपसमुच्चय संरचना बनाता है।
- create_with_capacity(n): नई उपसमुच्चय संरचना बनाता है, प्रारंभ में रिक्त किन्तु n तत्वों तक धारण करने में सक्षम होते है।
add(S,x): तत्व x को S में जोड़ता है, यदि यह पहले से मौजूद नहीं है।
remove(S, x): तत्व x को S से विस्थापित करता है, यदि यह उपस्थित है।
capacity(S): S द्वारा धारण किए जा सकने वाले मानों की अधिकतम संख्या लौटाता है।

कुछ उपसमुच्चय संरचनाएं इनमें से केवल कुछ परिचालनों की अनुमति दे सकती हैं। प्रत्येक संचालन के वित्त कार्यान्वयन पर निर्भर करेगी, एवं संभवतः उपसमुच्चय में संग्रहीत विशेष मूल्यों पर भी, एवं जिस क्रम में उन्हें सम्मिलित किया गया है।

अतिरिक्त संचालन

ऐसे कई अन्य संचालन हैं जिन्हें (सिद्धांत रूप में) उपरोक्त के संदर्भ में परिभाषित किया जा सकता है, जैसे:

pop(S): एस का एक मनमाना तत्व लौटाता है, इसे एस से हटा देता है।^[1]
pick(S): S का मनमाना तत्व लौटाता है।^[2]^[3]^[4] कार्यात्मक रूप से, उत्परिवर्ती pop चयनकर्ताओं की जोड़ी के रूप में व्याख्या की जा सकती है (pick, rest), कहाँ rest मनमाने तत्व को छोड़कर सभी तत्वों से युक्त उपसमुच्चय लौटाता है।^[5] के रूप में समझा जा सकता है iterate.^{[lower-alpha 1]}
map(F,S): फ़ंक्शन F को S के प्रत्येक तत्व पर प्रारम्भ करने के परिणामस्वरूप भिन्न मानों का उपसमुच्चय लौटाता है।
filter(P,S): एस के सभी तत्वों से युक्त सबउपसमुच्चय लौटाता है जो किसी दिए गए विधेय (गणितीय तर्क) पी को संतुष्ट करता है।
fold(A₀,F,S): मान A लौटाता है_|S| आवेदन करने के पश्चात A_i+1 := F(A_i, e) एस के प्रत्येक तत्व ई के लिए, कुछ बाइनरी संचालन एफ के लिए। एफ को अच्छी प्रकार से परिभाषित करने के लिए सहयोगी एवं कम्यूटेटिव होना चाहिए।
clear(S): एस के सभी तत्वों को हटा दें।
equal(S₁', S₂'): जांचता है कि क्या दिए गए दो उपसमुच्चय समान हैं (अर्थात सभी एवं केवल समान तत्व सम्मिलित हैं)।
hash(S): स्थिर उपसमुच्चय S के लिए एक मिश्रण मान लौटाता है जैसे कि if equal(S₁, S₂) तब hash(S₁) = hash(S₂)

अन्य कार्यों को एक विशेष प्रकार के तत्वों वाले उपसमुच्चय के लिए परिभाषित किया जा सकता है:

sum(S): योग की कुछ परिभाषा के लिए S के सभी तत्वों का योग लौटाता है। उदाहरण के लिए, पूर्णांक या वास्तविक से अधिक, इसे इस रूप में परिभाषित किया जा सकता है fold(0, add, S).
collapse(S): उपसमुच्चय का एक उपसमुच्चय दिया गया है, संघ वापस करें।^[6] उदाहरण के लिए, collapse({{1}, {2, 3}}) == {1, 2, 3}. प्रकार का माना जा सकता है sum.
flatten(S): उपसमुच्चय एवं परमाणु तत्वों (तत्व जो उपसमुच्चय नहीं हैं) से मिलकर एक उपसमुच्चय दिया गया है, एक उपसमुच्चय देता है जिसके तत्व मूल शीर्ष-स्तरीय उपसमुच्चय के परमाणु तत्व या उपसमुच्चय के तत्व होते हैं। दूसरे शब्दों में, नेस्टिंग के स्तर को हटा दें - जैसे collapse, किन्तु परमाणुओं की अनुमति दें। यह एक बार किया जा सकता है, या केवल परमाणु तत्वों का एक उपसमुच्चय प्राप्त करने के लिए पुनरावर्ती चपटा किया जा सकता है।^[7] उदाहरण के लिए, flatten({1, {2, 3}}) == {1, 2, 3}.
nearest(S,x): S का तत्व लौटाता है जो x के मूल्य में निकटतम है (कुछ मीट्रिक (गणित) द्वारा)।
min(S), max(S): S का न्यूनतम/अधिकतम तत्व लौटाता है।

कार्यान्वयन

विभिन्न डेटा संरचनाओं का उपयोग करके उपसमुच्चय को प्रारम्भ किया जा सकता है, जो विभिन्न कार्यों के लिए भिन्न-भिन्न समय एवं स्थान का समाधान प्रदान करते हैं। कुछ कार्यान्वयन अधिक विशिष्ट संचालन की दक्षता में सुधार के लिए चित्रित किए गए हैं, जैसे nearest या union. सामान्य उपयोग के रूप में वर्णित कार्यान्वयन सामान्यतः अनुकूलित करने का प्रयास करते हैं, element_of, add, एवं delete संचालन सरल कार्यान्वयन सूची (सार डेटा प्रकार) का उपयोग करना है, तत्वों के क्रम की अनदेखी करना एवं बार-बार मूल्यों से बचने के लिए ध्यान रखना, यह सरल किन्तु अक्षम है, क्योंकि उपसमुच्चय सदस्यता या तत्व विलोपन जैसे संचालन O (N) हैं, क्योंकि उन्हें पूर्ण रूप से सूची को स्कैन करने की आवश्यकता होती है।^{[lower-alpha 2]} उपसमुच्चय को प्रायः अधिक कुशल डेटा संरचनाओं का उपयोग करके कार्यान्वित किया जाता है।

जैसा कि उपसमुच्चय को मानचित्र (संकेतक फ़ंक्शन द्वारा) के रूप में व्याख्या किया जा सकता है, उपसमुच्चय सामान्यतः उसी प्रकार (आंशिक) मानचित्र (सहयोगी सरणियाँ) में प्रारम्भ होते हैं - इस विषय में जिसमें प्रत्येक कुंजी-मूल्य जोड़ी का मान होता है इकाई प्रकार या प्रहरी मान (जैसे 1) - अर्थात्, क्रमबद्ध उपसमुच्चयों के लिए स्व-संतुलन बाइनरी परिक्षण वृक्ष (जिसमें अधिकांश संचालनों के लिए O(log n) है), या अनसोल्ड उपसमुच्चय के लिए मिश्रण सारणी (जिसमें O(1) औसत-परिस्थिति है, किन्तु O(n) सबसे निकृष्ट-परिस्थिति, अधिकांश संचालनों के लिए) क्रमबद्ध रैखिक निकृष्ट-परिस्थिति^[8] नियतात्मक रूप से आदेशित उपसमुच्चय प्रदान करने के लिए उपयोग किया जा सकता है।

इसके अतिरिक्त, उन भाषाओं में जो नक्शों का समर्थन करती हैं किन्तु उपसमुच्चय का नहीं, उपसमुच्चय को नक्शों के संदर्भ में प्रारम्भ किया जा सकता है। उदाहरण के लिए, पर्ल में सामान्य प्रोग्रामिंग मुहावरा जो सरणी को मिश्रण में परिवर्तित करता है जिसका मूल्य प्रहरी मान 1 है। उपसमुच्चय के रूप में उपयोग के लिए:

my %elements = map { $_ => 1 } @elements;

अन्य लोकप्रिय विधियों में सरणी डेटा संरचना सम्मिलित है। विशेष रूप से पूर्णांक 1..n का उपसमुच्चय n- बिट सरणी के रूप में कुशलतापूर्वक कार्यान्वित किया जा सकता है, जो अधिक ही कुशल संघ एवं चौराहे के संचालन का भी समर्थन करता है।ब्लूम नक्शा अधिक ही ठोस प्रतिनिधित्व का उपयोग करते हुए संभावित रूप से उपसमुच्चय को प्रारम्भ करता है, किन्तु प्रश्नों पर झूठी सकारात्मकता की अल्प संभावना को संकट में डालता है।

बूलियन उपसमुच्चय संचालनों को अधिक प्राथमिक संचालनों के संदर्भ में कार्यान्वित किया जा सकता है (pop, clear, एवं add), किन्तु विशेष एल्गोरिदम अर्घ्य स्पर्शोन्मुख समय सीमा उत्पन्न कर सकते हैं। यदि उपसमुच्चय को क्रम की गई सूचियों के रूप में कार्यान्वित किया जाता है, उदाहरण के लिए, भोली एल्गोरिथ्म के लिए union(S,T) S की लंबाई m गुणा T की लंबाई n के अनुपात में समय लगेगा, जबकि मर्ज एल्गोरिथम का संस्करण m+n के आनुपातिक समय में कार्य करेगा। इसके अतिरिक्त, विशेष उपसमुच्चय डेटा संरचनाएं हैं (जैसे कि संघ-शोध एल्गोरिथ्म ) जो दूसरों के मूल्य पर इनमें से अधिक संचालन के लिए अनुकूलित हैं।

भाषा समर्थन

पास्कल प्रोग्रामिंग भाषा उपसमुच्चय का समर्थन करने वाली प्रारंभिक भाषाओं में से थी; कई भाषाओं में अब यह सम्मिलित है, मूल भाषा में हो या किसी मानक पुस्तकालय में होता है।

C++ में, मानक टेम्पलेट पुस्तकालय (STL) प्रदान करती है set टेम्प्लेट कक्ष, जिसे सामान्यतः बाइनरी सर्च ट्री (जैसे लाल-काले पेड़) का उपयोग करके प्रारम्भ किया जाता है; सिलिकॉन ग्राफिक्स इंटरनेशनल का एसटीएल भी प्रदान करता है hash_set टेम्प्लेट कक्ष, जो मिश्रण तालिका का उपयोग करके एक उपसमुच्चय को प्रारम्भ करता है। C++11 के लिए समर्थन है unordered_set टेम्प्लेट कक्ष, जिसे मिश्रण तालिका का उपयोग करके कार्यान्वित किया जाता है। उपसमुच्चय में, तत्व स्वयं कुंजी हैं, अनुक्रमित कंटेनरों के विपरीत, जहां तत्वों को उनकी (सापेक्ष या पूर्ण) स्थिति का उपयोग करके अभिगम किया जाता है। उपसमुच्चय तत्वों में शक्तिहीन क्रम होना चाहिए।
रस्ट (प्रोग्रामिंग भाषा) मानक पुस्तकालय सामान्य प्रदान HashSet एवं BTreeSet प्रकार करता है।
जावा (प्रोग्रामिंग भाषा) प्रदान करता है Set अंतरापृष्ठ (कंप्यूटर विज्ञान) उपसमुच्चय का समर्थन करने के लिए ( HashSet वर्ग इसे मिश्रण तालिका का उपयोग करके कार्यान्वित करता है), एवं SortedSet सॉर्ट किए गए उपसमुच्चयों का समर्थन करने के लिए उप-अंतराफलक( TreeSet वर्ग इसे बाइनरी सर्च ट्री का उपयोग करके कार्यान्वित करता है)।
ऐप्पल इंक की फाउंडेशन किट (कोको (एपीआई) का भाग) उद्देश्य C कक्ष प्रदान करती है NSSet, NSMutableSet, NSCountedSet, NSOrderedSet, एवं NSMutableOrderedSet. CoreFoundation API इनके लिए CFSet एवं CFMutableSet प्रकार प्रदान करता है। C (प्रोग्रामिंग भाषा) में उपयोग करते है।
पायथन (प्रोग्रामिंग भाषा) में अंतर्निहित है set एवं frozenset प्रकार 2.4 के पश्चात से, एवं पायथन 3.0 एवं 2.7 के पश्चात से, कर्ली-ब्रैकेट सिंटैक्स का उपयोग करके गैर-रिक्त उपसमुच्चय शाब्दिक का समर्थन करता है, जैसे: {x, y, z}; रिक्त उपसमुच्चय का उपयोग करके बनाया जाना चाहिए set(), क्योंकि पायथन उपयोग {} रिक्त शब्दकोश का प्रतिनिधित्व करने के लिए करता है।
.NET फ्रेमवर्क जेनेरिक प्रदान करता है HashSet एवं SortedSet कक्षाएं जो सामान्य ISet अंतराफलकको प्रारम्भ करती हैं।
स्मॉलटॉक की कक्ष पुस्तकालय में सम्मिलित हैं Set एवं IdentitySetसमावेशन परीक्षण के लिए क्रमशः समानता एवं पहचान का उपयोग करना, कई बोलियाँ संपीडित भंडारण के लिए भिन्नताएँ प्रदान करती हैं (NumberSet, CharacterSet), ऑर्डर करने के लिए (OrderedSet, SortedSet, आदि) या शक्तिहीन संदर्भ (WeakIdentitySet) के लिए होता है ।
रूबी (प्रोग्रामिंग भाषा) के मानक पुस्तकालय में a set सम्मिलित है, Set एवं SortedSetमॉड्यूल जिसमें सम्मिलित है कक्षाएं जो मिश्रण तालिका का उपयोग करके उपसमुच्चय को प्रारम्भ करती हैं, पश्चात वाले क्रमबद्ध क्रम में पुनरावृत्ति की अनुमति देते हैं।
OCaml की मानक पुस्तकालय में a सम्मिलित होता है, Set मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके कार्यात्मक उपसमुच्चय डेटा संरचना को प्रारम्भ करता है।
हास्केल (प्रोग्रामिंग भाषा) का ग्लासगो हास्केल कंपाइलर कार्यान्वयन प्रदान करता है Data.Set मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके अपरिवर्तनीय उपसमुच्चय को प्रारम्भ करता है।^[9]
Tcl Tcllib पैकेज उपसमुच्चय मॉड्यूल प्रदान करता है जो TCL सूचियों के आधार पर उपसमुच्चय डेटा संरचना को प्रारम्भ करता है।
स्विफ्ट (प्रोग्रामिंग भाषा) a Set प्रकार, स्विफ्ट 1.2 के पश्चात से।स्टैंडर्ड पुस्तकालय में होता है।
जावास्क्रिप्ट Set ईसीएमएस्क्रिप्ट 2015 के साथ मानक अंतर्निर्मित वस्तु के रूप में प्रस्तुत किया ^[10] है।
Erlang (प्रोग्रामिंग भाषा) की मानक पुस्तकालय में a sets मापांक होता है।
क्लोजर में मिश्रण उपसमुच्चय के लिए शाब्दिक सिंटैक्स है, एवं सॉर्ट किए गए उपसमुच्चय को भी प्रारम्भ करता है।
LabVIEW के निकट संस्करण 2019 से उपसमुच्चय के लिए मूल समर्थन है।
एडा (प्रोग्रामिंग भाषा) Ada.Containers.Hashed_Sets एवं Ada.Containers.Ordered_Sets संकुल प्रदान करता है।

जैसा कि पूर्व खंड में उल्लेख किया गया है, उन भाषाओं में जो साधारण उपसमुच्चय का समर्थन नहीं करते हैं, किन्तु साहचर्य सरणियों का समर्थन करते हैं, तत्वों को कुंजियों के रूप में उपयोग करके, एवं मूल्यों के रूप में डमी मान का उपयोग करके उपसमुच्चय को साहचर्य सरणियों का उपयोग करके अनुकरण किया जा सकता है, जिन्हें अनदेखा किया जाता है।

बहुसमुच्चय

उपसमुच्चय की धारणा का सामान्यीकरण बहुसमुच्चय या बैग का है, जो उपसमुच्चय के समान है किन्तु बार-बार मान की अनुमति देता है। इसका उपयोग दो भिन्न-भिन्न अर्थों में किया जाता है: या तो समान मानों को समान माना जाता है एवं उन्हें केवल गिना जाता है, या समान मानों को समतुल्य माना जाता है एवं भिन्न-भिन्न वस्तुओं के रूप में संग्रहीत किया जाता है। उदाहरण के लिए, लोगों की सूची (नाम से) एवं उम्र (वर्षों में) दी गई है, कोई भी उम्र के बहुसमुच्चय का निर्माण कर सकता है, जो कि किसी दिए गए उम्र के लोगों की संख्या की गणना करता है। वैकल्पिक रूप से, कोई लोगों का बहुसमुच्चय बना सकता है, जहां दो लोगों को समान माना जाता है यदि उनकी आयु समान है (किन्तु भिन्न-भिन्न लोग हो सकते हैं एवं भिन्न-भिन्न नाम हो सकते हैं), इस विषय में प्रत्येक जोड़ी (नाम, आयु) को संग्रहित किया जाना चाहिए, एवं चयन करना दी गई आयु पर दी गई आयु के सभी लोगों को देता है।

औपचारिक रूप से, कंप्यूटर विज्ञान में वस्तुओं के लिए कुछ तुल्यता संबंध के अनुसार समान माना जाना संभव है किन्तु अन्य संबंध के अनुसार भिन्न है। कुछ प्रकार के बहुसमुच्चय कार्यान्वयन भिन्न-भिन्न समान वस्तुओं को डेटा संरचना में भिन्न-भिन्न वस्तुओं के रूप में संग्रहीत करेंगे; जबकि अन्य इसे संस्करण में संक्षिप्त कर देंगे एवं तत्व की बहुलता की सकारात्मक पूर्णांक गणना रखेंगे।

उपसमुच्चय के साथ, बहुसमुच्चय स्वाभाविक रूप से मिश्रण तालिका या पेड़ों का उपयोग करके कार्यान्वित किया जा सकता है, जो विभिन्न प्रदर्शन विशेषताओं को उत्पन्न करता है।

टाइप टी पर सभी बैग का उपसमुच्चय अभिव्यक्ति बैग टी द्वारा दिया गया है। यदि बहुसमुच्चय द्वारा कोई समान वस्तुओं को समान मानता है एवं उन्हें सरलता से गिनता है, तो बहुसमुच्चय को इनपुट डोमेन से गैर-नकारात्मक पूर्णांक (प्राकृतिक) के फ़ंक्शन के रूप में व्याख्या किया जा सकता है संख्या), इसके सूचक समारोह के साथ उपसमुच्चय की पहचान को सामान्यीकृत करना, कुछ स्थितियों में इस गिनती के अर्थ में बहुसमुच्चय को नकारात्मक मूल्यों की अनुमति देने के लिए सामान्यीकृत किया जा सकता है, जैसा कि पायथन में है।

C++ की मानक टेम्पलेट पुस्तकालय चयन किए गए एवं अवर्गीकृत बहुसमुच्चय दोनों को प्रारम्भ करती है। यह multiset क्रमबद्ध बहुसमुच्चय के लिए कक्ष प्रदान करता है, सहयोगी कंटेनर (C ++) के रूप में, जो स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करके इस बहुसमुच्चय को प्रारम्भ करता है। यह unordered_multiset अनियंत्रित सहयोगी कंटेनर (C ++)C++) के रूप में अवर्गीकृत बहुसमुच्चय के लिए कक्ष प्रदान करता है, जो मिश्रण तालिका का उपयोग करके इस बहुसमुच्चय को प्रारम्भ करता है। अवर्गीकृत बहुसमुच्चय C++11 के अनुसार मानक है; प्रथम SGI का STL प्रदान करता है hash_multiset कक्ष, जिसे कॉपी किया गया एवं अंततः मानकीकृत किया गया।
जावा (प्रोग्रामिंग भाषा) के लिए, तृतीय-पक्ष पुस्तकालय बहुसमुच्चय कार्यक्षमता प्रदान करते हैं।
- अपेक जन संग्रह Bag एवं SortedBag अंतरापृष्ठ, जैसे कक्षाओं को प्रारम्भ करने के साथ HashBag एवं TreeBagप्रदान करता है।
- Google Multiset अंतरापृष्ठ, जैसे कक्षाओं को प्रारम्भ करने के साथ अमरुद HashMultiset एवं TreeMultiset प्रदान करता है।
सेब प्रदान करता है NSCountedSet कोको (एपीआई) के रूप में कक्ष, प्रकार CFBag एवं CFMutableBag कोर फाउंडेशन के रूप में प्रदान करता है।
पायथन (प्रोग्रामिंग भाषा) पायथन के मानक पुस्तकालय में सम्मिलित हैं collections.Counter, जो बहुसमुच्चय के समान है।
स्मॉलटाक में Bagसम्मिलित हैं,वर्ग जिसे समावेशन परीक्षण के लिए विधेय के रूप में या तो पहचान या समानता का उपयोग करने के लिए तत्काल किया जा सकता है।

जहां बहुसमुच्चय डेटा संरचना उपलब्ध नहीं है, नियमित उपसमुच्चय का उपयोग करने के लिए वर्कअराउंड है, किन्तु भिन्न-भिन्न वस्तुओं पर सदैव समान नहीं होने के लिए समानता की भविष्यवाणी को ओवरराइड करता है (चूंकि, यह अभी भी उसी की कई घटनाओं को एकत्र करने में सक्षम नहीं होगा ) या उनके पूर्णांक गुणकों के मानों को मैप करने के लिए साहचर्य सरणी का उपयोग करें (यह समान तत्वों के बीच अंतर करने में सक्षम नहीं होगा)।

बैग पर विशिष्ट संचालन:

contains(B, x): जांचता है कि बैग बी में तत्व एक्स मौजूद है (कम से कम एक बार)।
is_sub_bag(B₁, B₂): जांचता है कि बैग बी में प्रत्येक तत्व है या नहीं₁ बी में होता है₁ बैग बी में होने की तुलना में अधिक बार नहीं₂; कभी-कभी बी के रूप में दर्शाया जाता है₁ ⊑ बी₂.
count(B, x): तत्व x के बैग B में होने की संख्या लौटाता है; कभी-कभी बी # एक्स के रूप में दर्शाया जाता है।
scaled_by(B, n): एक प्राकृतिक संख्या n दिया गया है, एक बैग लौटाता है जिसमें बैग बी के समान तत्व होते हैं, सिवाय इसके कि प्रत्येक तत्व जो बी में एम बार होता है परिणामी बैग में एन * एम बार होता है; कभी-कभी n ⊗ B के रूप में निरूपित किया जाता है।
union(B₁, B₂): एक बैग देता है जिसमें केवल वे मान होते हैं जो बैग बी में होते हैं₁ या बैग बी₂, सिवाय इसके कि परिणामस्वरूप बैग में मूल्य x की संख्या बराबर होती है (बी₁ # एक्स) + (बी₂ # एक्स); कभी-कभी बी के रूप में दर्शाया जाता है₁ ⊎ बी₂.

=== SQL === में बहुसमुच्चय संबंधपरक डेटाबेस प्रबंधन प्रणाली में, एक तालिका एक (गणितीय) उपसमुच्चय या एक बहुसमुच्चय हो सकती है, जो कुछ स्तंभों पर एकता की कमी की उपस्थिति पर निर्भर करता है (जो इसे एक उम्मीदवार कुंजी में बदल देता है)।

एसक्यूएल एक रिलेशनल तालिका से पंक्तियों के चयन की अनुमति देता है: यह संचालन सामान्य रूप से एक बहुसमुच्चय उत्पन्न करेगा, जब तक कि कीवर्ड DISTINCT पंक्तियों को सभी भिन्न-भिन्न होने के लिए मजबूर करने के लिए प्रयोग किया जाता है, या चयन में प्राथमिक (या उम्मीदवार) कुंजी सम्मिलित होती है।

एसक्यूएल # मानकीकरण इतिहास में MULTISET उप-क्वेरी को संग्रह अभिव्यक्ति में बदलने के लिए कीवर्ड का उपयोग किया जा सकता है:

SELECT expression1, expression2... FROM table_name...

एक सामान्य चयन है जिसका उपयोग किसी अन्य सामान्य क्वेरी की सबक्वेरी अभिव्यक्ति के रूप में किया जा सकता है, जबकि

MULTISET(SELECT expression1, expression2... FROM table_name...)

सबक्वायरी को एक संग्रह अभिव्यक्ति में बदल देता है जिसका उपयोग किसी अन्य क्वेरी में या उचित संग्रह प्रकार के कॉलम में असाइनमेंट में किया जा सकता है।

यह भी देखें

↑
For example, in Python pick can be implemented on a derived class of the built-in set as follows:
```
class Set(set):
    def pick(self):
        return next(iter(self))
```
↑ Element insertion can be done in O(1) time by simply inserting at an end, but if one avoids duplicates this takes O(n) time.

संदर्भ

↑ Python: pop()
↑ Management and Processing of Complex Data Structures: Third Workshop on Information Systems and Artificial Intelligence, Hamburg, Germany, February 28 - March 2, 1994. Proceedings, ed. Kai v. Luck, Heinz Marburger, p. 76
↑ Python Issue7212: Retrieve an arbitrary element from a set without removing it; see msg106593 regarding standard name
↑ Ruby Feature #4553: Add Set#pick and Set#pop
↑ Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning, Ute Schmid, Springer, Aug 21, 2003, p. 240
↑ Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop, S. Margherita, Italy, May 30 - June 3, 1994. Selected Papers, Volume 10, ed. Egidio Astesiano, Gianna Reggio, Andrzej Tarlecki, p. 38
↑ Ruby: flatten()
↑ Wang, Thomas (1997), Sorted Linear Hash Table, archived from the original on 2006-01-12
↑ Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993. Retrieved on 2015-03-11.
↑ "ECMAScript 2015 Language Specification – ECMA-262 6th Edition". www.ecma-international.org (in British English). Retrieved 2017-07-11.

[6] For example, in Python pick can be implemented on a derived class of the built-in set as follows:
class Set(set): def pick(self): return next(iter(self))

[9] Element insertion can be done in O(1) time by simply inserting at an end, but if one avoids duplicates this takes O(n) time.

[1] Python: pop()

[2] Management and Processing of Complex Data Structures: Third Workshop on Information Systems and Artificial Intelligence, Hamburg, Germany, February 28 - March 2, 1994. Proceedings, ed. Kai v. Luck, Heinz Marburger, p. 76

[3] Python Issue7212: Retrieve an arbitrary element from a set without removing it; see msg106593 regarding standard name

[4] Ruby Feature #4553: Add Set#pick and Set#pop

[5] Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning, Ute Schmid, Springer, Aug 21, 2003, p. 240

[7] Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop, S. Margherita, Italy, May 30 - June 3, 1994. Selected Papers, Volume 10, ed. Egidio Astesiano, Gianna Reggio, Andrzej Tarlecki, p. 38

[8] Ruby: flatten()

[10] Wang, Thomas (1997), Sorted Linear Hash Table, archived from the original on 2006-01-12

[11] Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993. Retrieved on 2015-03-11.

[12] "ECMAScript 2015 Language Specification – ECMA-262 6th Edition". www.ecma-international.org (in British English). Retrieved 2017-07-11.

[1]

[2]

[3]

[4]

[5]

[lower-alpha 1]

[6]

[7]

[lower-alpha 2]

[8]

[9]

[10]

@@ Line 82: / Line 82: @@
 * [[C++]] में, [[मानक टेम्पलेट लाइब्रेरी|मानक टेम्पलेट  पुस्तकालय]] (STL) प्रदान करती है <code>[[set (C++)|set]]</code> टेम्प्लेट कक्ष, जिसे सामान्यतः बाइनरी सर्च ट्री (जैसे लाल-काले पेड़) का उपयोग करके प्रारम्भ किया जाता है; [[सिलिकॉन ग्राफिक्स इंटरनेशनल]] का एसटीएल भी प्रदान करता है <code>hash_set</code> टेम्प्लेट कक्ष, जो मिश्रण तालिका का उपयोग करके एक उपसमुच्चय को प्रारम्भ करता है। [[C++11]] के लिए समर्थन है <code>[[unordered_set (C++)|unordered_set]]</code> टेम्प्लेट कक्ष, जिसे मिश्रण तालिका का उपयोग करके कार्यान्वित किया जाता है। उपसमुच्चय में, तत्व स्वयं कुंजी हैं, अनुक्रमित कंटेनरों के विपरीत, जहां तत्वों को उनकी (सापेक्ष या पूर्ण) स्थिति का उपयोग करके अभिगम किया जाता है। उपसमुच्चय तत्वों में शक्तिहीन क्रम होना चाहिए।
 * रस्ट (प्रोग्रामिंग भाषा) मानक पुस्तकालय सामान्य प्रदान  <code>[https://doc.rust-lang.org/std/collections/struct.HashSet.html HashSet]</code> एवं <code>[https://doc.rust-lang.org/std/collections/struct.BTreeSet.html BTreeSet]</code> प्रकार करता है।
-* [[जावा (प्रोग्रामिंग भाषा)]] प्रदान करता है {{Javadoc:SE|java/util|Set}} [[इंटरफ़ेस (कंप्यूटर विज्ञान)]] उपसमुच्चय का समर्थन करने के लिए ( {{Javadoc:SE|java/util|HashSet}} वर्ग इसे मिश्रण तालिका का उपयोग करके कार्यान्वित करता है), एवं {{Javadoc:SE|java/util|SortedSet}} सॉर्ट किए गए उपसमुच्चयों का समर्थन करने के लिए उप-अंतराफलक( {{Javadoc:SE|java/util|TreeSet}} वर्ग इसे बाइनरी सर्च ट्री का उपयोग करके कार्यान्वित करता है)।
+* [[जावा (प्रोग्रामिंग भाषा)]] प्रदान करता है {{Javadoc:SE|java/util|Set}} [[इंटरफ़ेस (कंप्यूटर विज्ञान)|अंतरापृष्ठ (कंप्यूटर विज्ञान)]] उपसमुच्चय का समर्थन करने के लिए ( {{Javadoc:SE|java/util|HashSet}} वर्ग इसे मिश्रण तालिका का उपयोग करके कार्यान्वित करता है), एवं {{Javadoc:SE|java/util|SortedSet}} सॉर्ट किए गए उपसमुच्चयों का समर्थन करने के लिए उप-अंतराफलक( {{Javadoc:SE|java/util|TreeSet}} वर्ग इसे बाइनरी सर्च ट्री का उपयोग करके कार्यान्वित करता है)।
 * ऐप्पल इंक की [[फाउंडेशन किट]] ([[कोको (एपीआई)]] का भाग) [[ उद्देश्य सी | उद्देश्य C]] कक्ष प्रदान करती है <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSSet_Class/ NSSet]</code>, <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSMutableSet_Class/ NSMutableSet]</code>, <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSCountedSet_Class/ NSCountedSet]</code>, <code>[https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSOrderedSet_Class/Reference/Reference.html NSOrderedSet]</code>, एवं <code>[https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSMutableOrderedSet_Class/Reference/Reference.html NSMutableOrderedSet]</code>. [[CoreFoundation]] API इनके लिए [https://developer.apple.com/documentation/CoreFoundation/Reference/CFSetRef/ CFSet] एवं [https://developer.apple.com/documentation/CoreFoundation/Reference/CFMutableSetRef/ CFMutableSet] प्रकार प्रदान करता है। [[सी (प्रोग्रामिंग भाषा)|C (प्रोग्रामिंग भाषा)]] में उपयोग करते है।
 * [[पायथन (प्रोग्रामिंग भाषा)]] में अंतर्निहित है [https://docs.python.org/library/stdtypes.html#set-types-set-frozenset <code>set</code> एवं <code>frozenset</code> प्रकार] 2.4 के पश्चात से, एवं पायथन 3.0 एवं 2.7 के पश्चात से, कर्ली-ब्रैकेट सिंटैक्स का उपयोग करके गैर-रिक्त उपसमुच्चय शाब्दिक का समर्थन करता है, जैसे: <code>{x, y, z}</code>; रिक्त उपसमुच्चय का उपयोग करके बनाया जाना चाहिए <code>set()</code>, क्योंकि पायथन उपयोग <code>{}</code> रिक्त शब्दकोश का प्रतिनिधित्व करने के लिए करता है।
@@ Line 112: / Line 112: @@
 * C++ की मानक टेम्पलेट  पुस्तकालय चयन किए गए एवं अवर्गीकृत बहुसमुच्चय दोनों को प्रारम्भ करती है। यह <code>[[Multiset (C++)|multiset]]</code> क्रमबद्ध बहुसमुच्चय के लिए कक्ष प्रदान करता है, [[सहयोगी कंटेनर (सी ++)|सहयोगी कंटेनर (C ++)]] के रूप में, जो स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करके इस बहुसमुच्चय को प्रारम्भ करता है। यह <code>unordered_multiset</code> [[अनियंत्रित सहयोगी कंटेनर (सी ++)|अनियंत्रित सहयोगी कंटेनर (C ++)]]C++) के  रूप में अवर्गीकृत बहुसमुच्चय के लिए कक्ष प्रदान करता है, जो मिश्रण तालिका का उपयोग करके इस बहुसमुच्चय को प्रारम्भ करता है। अवर्गीकृत बहुसमुच्चय C++11 के अनुसार मानक है; प्रथम SGI का STL प्रदान करता है <code>hash_multiset</code> कक्ष, जिसे कॉपी किया गया एवं अंततः मानकीकृत किया गया।
-* जावा (प्रोग्रामिंग भाषा) के लिए, तृतीय-पक्ष पुस्तकालय बहुसमुच्चय कार्यक्षमता प्रदान करते हैं:
+* जावा (प्रोग्रामिंग भाषा) के लिए, तृतीय-पक्ष पुस्तकालय बहुसमुच्चय कार्यक्षमता प्रदान करते हैं।
-** [[अपाचे कॉमन्स]] कलेक्शंस प्रदान करता है <code>[https://web.archive.org/web/20150109083430/https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/Bag.html Bag]</code> एवं <code>SortedBag</code> इंटरफेस, जैसे कक्षाओं को प्रारम्भ करने के साथ <code>HashBag</code> एवं <code>TreeBag</code>.
+** [[अपाचे कॉमन्स|अपेक जन]] संग्रह <code>[https://web.archive.org/web/20150109083430/https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/Bag.html Bag]</code> एवं <code>SortedBag</code>  अंतरापृष्ठ, जैसे कक्षाओं को प्रारम्भ करने के साथ <code>HashBag</code> एवं <code>TreeBag</code>प्रदान करता है।
-** Google अमरूद प्रदान करता है <code>[https://google.github.io/guava/releases/20.0/api/docs/com/google/common/collect/Multiset.html Multiset]</code> इंटरफ़ेस, जैसे कक्षाओं को प्रारम्भ करने के साथ <code>[https://guava.dev/releases/20.0/api/docs/com/google/common/collect/HashMultiset.html HashMultiset]</code> एवं <code>[https://guava.dev/releases/20.0/api/docs/com/google/common/collect/TreeMultiset.html TreeMultiset]</code>.
+** Google <code>[https://google.github.io/guava/releases/20.0/api/docs/com/google/common/collect/Multiset.html Multiset]</code> अंतरापृष्ठ, जैसे कक्षाओं को प्रारम्भ करने के साथ अमरुद <code>[https://guava.dev/releases/20.0/api/docs/com/google/common/collect/HashMultiset.html HashMultiset]</code> एवं <code>[https://guava.dev/releases/20.0/api/docs/com/google/common/collect/TreeMultiset.html TreeMultiset]</code> प्रदान करता है।
-* सेब प्रदान करता है <code>[https://developer.apple.com/documentation/foundation/nscountedset NSCountedSet]</code> कोको (एपीआई) के हिस्से के रूप में कक्ष, एवं <code>[https://developer.apple.com/documentation/corefoundation/cfbag-s1l CFBag]</code> एवं <code>[https://developer.apple.com/documentation/corefoundation/cfmutablebag-rqn CFMutableBag]</code> CoreFoundation के हिस्से के रूप में प्रकार।
+* सेब प्रदान करता है <code>[https://developer.apple.com/documentation/foundation/nscountedset NSCountedSet]</code> कोको (एपीआई) के रूप में कक्ष, प्रकार <code>[https://developer.apple.com/documentation/corefoundation/cfbag-s1l CFBag]</code> एवं <code>[https://developer.apple.com/documentation/corefoundation/cfmutablebag-rqn CFMutableBag]</code> कोर फाउंडेशन के रूप में  प्रदान करता है।
-* पायथन (प्रोग्रामिंग भाषा)|पायथन के मानक पुस्तकालय में सम्मिलित हैं <code>[https://docs.python.org/library/collections.html#collections.Counter collections.Counter]</code>, जो एक बहुसमुच्चय के समान है।
+* पायथन (प्रोग्रामिंग भाषा) पायथन के मानक पुस्तकालय में सम्मिलित हैं <code>[https://docs.python.org/library/collections.html#collections.Counter collections.Counter]</code>, जो बहुसमुच्चय के समान है।
-* स्मॉलटाक में सम्मिलित हैं <code>Bag</code> वर्ग, जिसे समावेशन परीक्षण के लिए विधेय के रूप में या तो पहचान या समानता का उपयोग करने के लिए तत्काल किया जा सकता है।
+* स्मॉलटाक में <code>Bag</code>सम्मिलित हैं,वर्ग जिसे समावेशन परीक्षण के लिए विधेय के रूप में या तो पहचान या समानता का उपयोग करने के लिए तत्काल किया जा सकता है।
-जहां एक बहुसमुच्चय डेटा संरचना उपलब्ध नहीं है, एक नियमित उपसमुच्चय का उपयोग करने के लिए एक वर्कअराउंड है, किन्तु भिन्न-भिन्न वस्तुओं पर हमेशा समान नहीं होने के लिए समानता की भविष्यवाणी को ओवरराइड करता है (हालांकि, यह अभी भी उसी की कई घटनाओं को स्टोर करने में सक्षम नहीं होगा ऑब्जेक्ट) या उनके पूर्णांक गुणकों के मानों को मैप करने के लिए एक साहचर्य सरणी का उपयोग करें (यह समान तत्वों के बीच अंतर करने में सक्षम नहीं होगा)।
+जहां बहुसमुच्चय डेटा संरचना उपलब्ध नहीं है, नियमित उपसमुच्चय का उपयोग करने के लिए वर्कअराउंड है, किन्तु भिन्न-भिन्न वस्तुओं पर सदैव समान नहीं होने के लिए समानता की भविष्यवाणी को ओवरराइड करता है (चूंकि, यह अभी भी उसी की कई घटनाओं को एकत्र करने में सक्षम नहीं होगा ) या उनके पूर्णांक गुणकों के मानों को मैप करने के लिए साहचर्य सरणी का उपयोग करें (यह समान तत्वों के बीच अंतर करने में सक्षम नहीं होगा)।
 बैग पर विशिष्ट संचालन:

v t e Data types
Uninterpreted	Bit Byte Trit Tryte Word Bit array
Numeric	Arbitrary-precision or bignum Complex Decimal Fixed point Floating point Reduced precision Minifloat Half precision bfloat16 Single precision Double precision Quadruple precision Octuple precision Extended precision Long double Integer signedness Interval Rational
Pointer	Address physical virtual Reference
Text	Character String null-terminated
Composite	Algebraic data type generalized Array Associative array Class Dependent Equality Inductive Intersection List Object metaobject Option type Product Record or Struct Refinement Set Union tagged
Other	Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Top type Type class Unit type Void
Related topics	Abstract data type Boxing Data structure Generic Kind metaclass Parametric polymorphism Primitive data type Interface Subtyping Type constructor Type conversion Type system Type theory Variable

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

सेट (अमूर्त डेटा प्रकार): Difference between revisions

Namespaces

More

Page actions

Revision as of 15:33, 18 May 2023

Contents

प्रकार सिद्धांत

संचालन

कोर उपसमुच्चय-सैद्धांतिक संचालन

स्थैतिक उपसमुच्चय

गतिशील उपसमुच्चय

अतिरिक्त संचालन

कार्यान्वयन

भाषा समर्थन

बहुसमुच्चय

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सेट (अमूर्त डेटा प्रकार): Difference between revisions

Revision as of 15:33, 18 May 2023

प्रकार सिद्धांत

संचालन

कोर उपसमुच्चय-सैद्धांतिक संचालन

स्थैतिक उपसमुच्चय

गतिशील उपसमुच्चय

अतिरिक्त संचालन

कार्यान्वयन

भाषा समर्थन

बहुसमुच्चय

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories