सेट (अमूर्त डेटा प्रकार): Difference between revisions
m (Abhishek moved page समुच्चय (अमूर्त डेटा प्रकार) to सेट (अमूर्त डेटा प्रकार) without leaving a redirect) |
No edit summary |
||
Line 1: | Line 1: | ||
{{Short description|Abstract data type for storing unique values}} | {{Short description|Abstract data type for storing unique values}} | ||
[[भारत]] [[कंप्यूटर विज्ञान]], | [[भारत]] [[कंप्यूटर विज्ञान]], सेट [[सार डेटा प्रकार]] है जो बिना किसी विशेष क्रम के अद्वितीय मूल्यों को संग्रहीत कर सकता है। यह परिमित समुच्चय की गणित अवधारणा का कंप्यूटर कार्यान्वयन है। अधिकांश अन्य [[संग्रह (सार डेटा प्रकार)]] प्रकारों के विपरीत, सेट से विशिष्ट तत्व को पुनः प्राप्त करने के अतिरिक्त, सामान्यतः सेट में सदस्यता के लिए मूल्य का परीक्षण किया जाता है। | ||
कुछ | कुछ सेट डेटा संरचनाएं स्थिर या एकत्रित सेट के लिए चित्रित किए गए हैं जो उनके निर्माण के पश्चात परिवर्तित नहीं होते हैं। स्थिर सेट स्वयं तत्वों पर केवल क्वेरी संचालन की अनुमति देते हैं - जैसे कि यह देखना कि क्या दिया गया मान सेट में है, या कुछ मनमाना क्रम में मानों की गणना करना अन्य वेरिएंट, जिन्हें डायनेमिक या म्यूतालिका सेट कहा जाता है, सेट से तत्वों को सम्मिलित करने एवं विस्थापित करने की भी अनुमति देते हैं। | ||
[[ multiset |बहुसमुच्चय]] विशेष प्रकार का | [[ multiset |बहुसमुच्चय]] विशेष प्रकार का सेट है, जिसमें तत्व सेट में कई बार दिखाई दे सकता है। | ||
== [[प्रकार सिद्धांत]] == | == [[प्रकार सिद्धांत]] == | ||
प्रकार सिद्धांत में, | प्रकार सिद्धांत में, सेट सामान्यतः उनके संकेतक फ़ंक्शन (विशेषता समारोह) के साथ पहचाने जाते हैं: तदनुसार, <math>A</math> प्रकार के मूल्यों का सेट <math>2^{A}</math> या <math>\mathcal{P}(A)</math> द्वारा दर्शाया जा सकता है। (उपप्रकार एवं सेट को [[शोधन प्रकार]] द्वारा प्रतिरूपित किया जा सकता है, एवं भागफल सेट को परिवर्तनीय सेट द्वारा प्रतिस्थापित किया जा सकता है।) विशेषता कार्य <math>F</math> सेट को <math>S</math> परिभाषित किया जाता है। | ||
:<math>F(x) = \begin{cases} | :<math>F(x) = \begin{cases} | ||
1, & \mbox{if } x \in S \\ | 1, & \mbox{if } x \in S \\ | ||
Line 13: | Line 13: | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
सिद्धांत रूप में, कई अन्य अमूर्त डेटा संरचनाओं को मानक संचालन पर लगाए गए अतिरिक्त संचालन एवंअतिरिक्त सिद्धांतों के साथ | सिद्धांत रूप में, कई अन्य अमूर्त डेटा संरचनाओं को मानक संचालन पर लगाए गए अतिरिक्त संचालन एवंअतिरिक्त सिद्धांतों के साथ सेट संरचनाओं के रूप में देखा जा सकता है। उदाहरण के लिए, अमूर्त हीप डेटा संरचना को सेट संरचना के रूप में देखा जा सकता है <code>min(''S'')</code> संचालन जो सबसे अल्प मूल्य का तत्व लौटाता है। | ||
== संचालन == | == संचालन == | ||
=== कोर | === कोर सेट-सैद्धांतिक संचालन === | ||
कोई | कोई सेट के बीजगणित के संचालन को परिभाषित कर सकता है: | ||
* <code>union(''S'',''T'')</code>: समुच्चय S एवं T का [[संघ (सेट | * <code>union(''S'',''T'')</code>: समुच्चय S एवं T का [[संघ (सेट सिद्धांत)]] लौटाता है। | ||
* <code>intersection(''S'',''T'')</code>: समुच्चय S एवं T का प्रतिच्छेदन ( | * <code>intersection(''S'',''T'')</code>: समुच्चय S एवं T का प्रतिच्छेदन (सेट सिद्धांत) लौटाता है। | ||
* <code>difference(''S'',''T'')</code>: समुच्चय S एवं T का [[अंतर (सेट | * <code>difference(''S'',''T'')</code>: समुच्चय S एवं T का [[अंतर (सेट सिद्धांत)]] लौटाता है। | ||
* <code>subset(''S'',''T'')</code>: विधेय जो परीक्षण करता है कि क्या समुच्चय S, समुच्चय T का | * <code>subset(''S'',''T'')</code>: विधेय जो परीक्षण करता है कि क्या समुच्चय S, समुच्चय T का सेट है। | ||
=== स्थैतिक | === स्थैतिक सेट === | ||
स्थैतिक | स्थैतिक सेट स्थिर S द्वारा प्रदान किए जा सकने वाले विशिष्ट संचालन हैं: | ||
* <code>is_element_of(''x'',''S'')</code>: परिक्षण किया जाता है कि क्या मान x | * <code>is_element_of(''x'',''S'')</code>: परिक्षण किया जाता है कि क्या मान x सेट S में है। | ||
* <code>is_empty(''S'')</code>: परिक्षण किया जाता है कि | * <code>is_empty(''S'')</code>: परिक्षण किया जाता है कि सेट S रिक्त है या नहीं। | ||
* <code>size(''S'')</code> या <code>[[cardinality]](''S'')</code>: एस में तत्वों की संख्या लौटाता है। | * <code>size(''S'')</code> या <code>[[cardinality]](''S'')</code>: एस में तत्वों की संख्या लौटाता है। | ||
* <code>[[iterator|iterate]](''S'')</code>: ऐसा फ़ंक्शन लौटाता है जो प्रत्येक आह्वान पर S का एवं कुछ मनमाना क्रम में मान देता है। | * <code>[[iterator|iterate]](''S'')</code>: ऐसा फ़ंक्शन लौटाता है जो प्रत्येक आह्वान पर S का एवं कुछ मनमाना क्रम में मान देता है। | ||
* <code>enumerate(''S'')</code>: कुछ मनमानी क्रम में S के तत्वों वाली सूची देता है। | * <code>enumerate(''S'')</code>: कुछ मनमानी क्रम में S के तत्वों वाली सूची देता है। | ||
* <code>build(''x''<sub>1</sub>,''x''<sub>2</sub>,…,''x''<sub>''n''</sub>,)</code>: मान x के साथ ''x''<sub>1</sub>,''x''<sub>2</sub>,...,''x<sub>n</sub>'' | * <code>build(''x''<sub>1</sub>,''x''<sub>2</sub>,…,''x''<sub>''n''</sub>,)</code>: मान x के साथ ''x''<sub>1</sub>,''x''<sub>2</sub>,...,''x<sub>n</sub>'' सेट संरचना बनाता है। | ||
* <code>create_from(''collection'')</code>: दिए गए संग्रह के सभी तत्वों (सार डेटा प्रकार) या दिए गए पुनरावर्तक द्वारा लौटाए गए सभी तत्वों वाली नई | * <code>create_from(''collection'')</code>: दिए गए संग्रह के सभी तत्वों (सार डेटा प्रकार) या दिए गए पुनरावर्तक द्वारा लौटाए गए सभी तत्वों वाली नई सेट संरचना बनाता है। | ||
=== गतिशील | === गतिशील सेट === | ||
गतिशील | गतिशील सेट संरचनाएं सामान्यतः जोड़ती हैं, | ||
* <code>create()</code>: प्रारंभ में रिक्त | * <code>create()</code>: प्रारंभ में रिक्त सेट संरचना बनाता है। | ||
** <code>create_with_capacity(''n'')</code>: नई | ** <code>create_with_capacity(''n'')</code>: नई सेट संरचना बनाता है, प्रारंभ में रिक्त किन्तु n तत्वों तक धारण करने में सक्षम होते है। | ||
* <code>add(''S'',''x'')</code>: तत्व x को S में जोड़ता है, यदि यह पहले से उपस्थित नहीं है। | * <code>add(''S'',''x'')</code>: तत्व x को S में जोड़ता है, यदि यह पहले से उपस्थित नहीं है। | ||
* <code>remove(''S'', ''x'')</code>: तत्व x को S से विस्थापित करता है, यदि यह उपस्थित है। | * <code>remove(''S'', ''x'')</code>: तत्व x को S से विस्थापित करता है, यदि यह उपस्थित है। | ||
* <code>capacity(''S'')</code>: S द्वारा धारण किए जा सकने वाले मानों की अधिकतम संख्या लौटाता है। | * <code>capacity(''S'')</code>: S द्वारा धारण किए जा सकने वाले मानों की अधिकतम संख्या लौटाता है। | ||
कुछ | कुछ सेट संरचनाएं इनमें से केवल कुछ परिचालनों की अनुमति दे सकती हैं। प्रत्येक संचालन के वित्त कार्यान्वयन पर निर्भर करेगी, एवं संभवतः सेट में संग्रहीत विशेष मूल्यों पर भी, एवं जिस क्रम में उन्हें सम्मिलित किया गया है। | ||
=== अतिरिक्त संचालन === | === अतिरिक्त संचालन === | ||
ऐसे कई अन्य संचालन हैं जिन्हें (सिद्धांत रूप में) उपरोक्त के संदर्भ में परिभाषित किया जा सकता है, जैसे: | ऐसे कई अन्य संचालन हैं जिन्हें (सिद्धांत रूप में) उपरोक्त के संदर्भ में परिभाषित किया जा सकता है, जैसे: | ||
* <code>pop(''S'')</code>: | * <code>pop(''S'')</code>: S का एक मनमाना तत्व लौटाता है, इसे S से विस्थापित कर देता है।<ref>Python: [https://docs.python.org/3/library/stdtypes.html#set.pop pop()]</ref> | ||
* <code>pick(''S'')</code>: S का मनमाना तत्व लौटाता है।<ref>''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, [https://books.google.com/books?id=ymhoQ3y0vccC&q=pick&pg=PA76 p. 76]</ref><ref>Python [http://bugs.python.org/issue7212 Issue7212]: Retrieve an arbitrary element from a set without removing it; see [http://bugs.python.org/issue7212#msg106593 msg106593] regarding standard name</ref><ref>Ruby [https://bugs.ruby-lang.org/issues/4553 Feature #4553]: Add Set#pick and Set#pop</ref> कार्यात्मक रूप से, उत्परिवर्ती <code>pop</code> चयनकर्ताओं की जोड़ी के रूप में व्याख्या की जा सकती है <code>(pick, rest),</code> | * <code>pick(''S'')</code>: S का मनमाना तत्व लौटाता है।<ref>''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, [https://books.google.com/books?id=ymhoQ3y0vccC&q=pick&pg=PA76 p. 76]</ref><ref>Python [http://bugs.python.org/issue7212 Issue7212]: Retrieve an arbitrary element from a set without removing it; see [http://bugs.python.org/issue7212#msg106593 msg106593] regarding standard name</ref><ref>Ruby [https://bugs.ruby-lang.org/issues/4553 Feature #4553]: Add Set#pick and Set#pop</ref> कार्यात्मक रूप से, उत्परिवर्ती <code>pop</code> चयनकर्ताओं की जोड़ी के रूप में व्याख्या की जा सकती है <code>(pick, rest),</code> जहाँ <code>rest</code> मनमाने तत्व को त्यागकर सभी तत्वों से युक्त सेट लौटाता है।<ref>''Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning,'' Ute Schmid, Springer, Aug 21, 2003, [https://books.google.com/books?id=p-Fy25LE4lMC&q=pick&pg=PA240 p. 240]</ref> <code>iterate</code> के रूप में समझा जा सकता है। {{efn|For example, in Python <code>pick</code> can be implemented on a derived class of the built-in <code>set</code> as follows: | ||
<syntaxhighlight lang="python"> | <syntaxhighlight lang="python"> | ||
class Set(set): | class Set(set): | ||
def pick(self): | def pick(self): | ||
return next(iter(self))</syntaxhighlight>}} | return next(iter(self))</syntaxhighlight>}} | ||
* <code>[[Map (higher-order function)|map]](''F'',''S'')</code>: फ़ंक्शन F को S के प्रत्येक तत्व पर प्रारम्भ करने के परिणामस्वरूप भिन्न मानों का | * <code>[[Map (higher-order function)|map]](''F'',''S'')</code>: फ़ंक्शन F को S के प्रत्येक तत्व पर प्रारम्भ करने के परिणामस्वरूप भिन्न मानों का सेट लौटाता है। | ||
* <code>[[Filter (higher-order function)|filter]](''P'',''S'')</code>: s के सभी तत्वों से युक्त | * <code>[[Filter (higher-order function)|filter]](''P'',''S'')</code>: s के सभी तत्वों से युक्त सबसेट लौटाता है जो किसी दिए गए [[विधेय (गणितीय तर्क)]] p को संतुष्ट करता है। | ||
* <code>[[Fold (higher-order function)|fold]](''A''<sub>0</sub>,''F'',''S'')</code>: मान A<sub>|''S''|</sub> लौटाता है, आवेदन करने के पश्चात <code>''A''<sub>i+1</sub> := ''F''(''A<sub>i</sub>'', ''e'')</code> S के प्रत्येक तत्व ई के लिए, कुछ बाइनरी संचालन F के लिए F को अच्छी प्रकार से परिभाषित करने के लिए सहयोगी एवं कम्यूटेटिव होना चाहिए। | * <code>[[Fold (higher-order function)|fold]](''A''<sub>0</sub>,''F'',''S'')</code>: मान A<sub>|''S''|</sub> लौटाता है, आवेदन करने के पश्चात <code>''A''<sub>i+1</sub> := ''F''(''A<sub>i</sub>'', ''e'')</code> S के प्रत्येक तत्व ई के लिए, कुछ बाइनरी संचालन F के लिए F को अच्छी प्रकार से परिभाषित करने के लिए सहयोगी एवं कम्यूटेटिव होना चाहिए। | ||
* <code>clear(''S'')</code>: s के सभी तत्वों को विस्थापित कर दें। | * <code>clear(''S'')</code>: s के सभी तत्वों को विस्थापित कर दें। | ||
* <code>equal(''S''<sub>1</sub>', ''S''<sub>2</sub>')</code>: जांचता है कि क्या दिए गए दो | * <code>equal(''S''<sub>1</sub>', ''S''<sub>2</sub>')</code>: जांचता है कि क्या दिए गए दो सेट समान हैं (अर्थात सभी एवं केवल समान तत्व सम्मिलित हैं)। | ||
* <code>hash(''S'')</code>: स्थिर | * <code>hash(''S'')</code>: स्थिर सेट S के लिए [[हैश मान|मिश्रण मान]] लौटाता है जैसे कि if <code>equal(''S''<sub>1</sub>, ''S''<sub>2</sub>)</code> तब <code>hash(''S<sub>1</sub>'') = hash(''S<sub>2</sub>'') है।</code> | ||
अन्य कार्यों को विशेष प्रकार के तत्वों वाले | अन्य कार्यों को विशेष प्रकार के तत्वों वाले सेट के लिए परिभाषित किया जा सकता है: | ||
* <code>sum(''S'')</code>: योग की कुछ परिभाषा के लिए S के सभी तत्वों का योग लौटाता है। उदाहरण के लिए, पूर्णांक या वास्तविक से अधिक, इसे <code>fold(0, add, ''S'')</code> इस रूप में परिभाषित किया जा सकता है। | * <code>sum(''S'')</code>: योग की कुछ परिभाषा के लिए S के सभी तत्वों का योग लौटाता है। उदाहरण के लिए, पूर्णांक या वास्तविक से अधिक, इसे <code>fold(0, add, ''S'')</code> इस रूप में परिभाषित किया जा सकता है। | ||
* <code>collapse(''S'')</code>: | * <code>collapse(''S'')</code>: सेट का <code>sum</code>सेट दिया गया है, संघ वापस करें,<ref>''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, [https://books.google.com/books?id=LkvQYL23v1sC&q=collapse&pg=PA38 p. 38]</ref> उदाहरण के लिए, <code>collapse({{1}, {2, 3}}) == {1, 2, 3}</code>. प्रकार का माना जा सकता है। | ||
* <code>flatten(''S'')</code>: | * <code>flatten(''S'')</code>: सेट एवं परमाणु तत्वों (तत्व जो सेट नहीं हैं) से मिलकर सेट दिया गया है, सेट देता है जिसके तत्व मूल शीर्ष-स्तरीय सेट के परमाणु तत्व या सेट के तत्व होते हैं। दूसरे शब्दों में, नेस्टिंग के स्तर को विस्थापित कर दें - जैसे <code>collapse,</code> किन्तु परमाणुओं की अनुमति दें। यह किया जा सकता है, या केवल परमाणु तत्वों का सेट प्राप्त करने के लिए पुनरावर्ती किया जा सकता है।<ref>Ruby: [http://www.ruby-doc.org/stdlib-2.1.2/libdoc/set/rdoc/Set.html#method-i-flatten flatten()]</ref> उदाहरण के लिए, <code>flatten({1, {2, 3}}) == {1, 2, 3}</code>होता है। | ||
* <code>nearest(''S'',''x'')</code>: S का तत्व लौटाता है जो x के मूल्य में निकटतम है (कुछ [[मीट्रिक (गणित)]] द्वारा)। | * <code>nearest(''S'',''x'')</code>: S का तत्व लौटाता है जो x के मूल्य में निकटतम है (कुछ [[मीट्रिक (गणित)]] द्वारा)। | ||
* <code>min(''S'')</code>, <code>max(''S'')</code>: S का न्यूनतम/अधिकतम तत्व लौटाता है। | * <code>min(''S'')</code>, <code>max(''S'')</code>: S का न्यूनतम/अधिकतम तत्व लौटाता है। | ||
== कार्यान्वयन == | == कार्यान्वयन == | ||
विभिन्न [[डेटा संरचना]]ओं का उपयोग करके | विभिन्न [[डेटा संरचना]]ओं का उपयोग करके सेट को प्रारम्भ किया जा सकता है, जो विभिन्न कार्यों के लिए भिन्न-भिन्न समय एवं स्थान का समाधान प्रदान करते हैं। कुछ कार्यान्वयन अधिक विशिष्ट संचालन की दक्षता में सुधार के लिए चित्रित किए गए हैं, जैसे <code>nearest</code> या <code>union</code>. सामान्य उपयोग के रूप में वर्णित कार्यान्वयन सामान्यतः अनुकूलित करने का प्रयास करते हैं, <code>element_of</code>, <code>add</code>, एवं <code>delete</code> संचालन सरल कार्यान्वयन [[सूची (सार डेटा प्रकार)]] का उपयोग करना है, तत्वों के क्रम की अनदेखी करना एवं बार-बार मूल्यों से बचने के लिए ध्यान रखना, यह सरल किन्तु अक्षम है, क्योंकि सेट सदस्यता या तत्व विलोपन जैसे संचालन O (N) हैं, क्योंकि उन्हें पूर्ण रूप से सूची को स्कैन करने की आवश्यकता होती है।{{efn|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) - अर्थात्, क्रमबद्ध सेटों के लिए स्व-संतुलन बाइनरी परिक्षण वृक्ष (जिसमें अधिकांश संचालनों के लिए O(log n) है), या अनसोल्ड सेट के लिए मिश्रण सारणी (जिसमें O(1) औसत-परिस्थिति है, किन्तु O(n) सबसे निकृष्ट-परिस्थिति, अधिकांश संचालनों के लिए) क्रमबद्ध रैखिक [[हैश तालिका|निकृष्ट-परिस्थिति]]<ref>{{Citation |title=Sorted Linear Hash Table |first1=Thomas |last1=Wang |url=http://www.concentric.net/~Ttwang/tech/sorthash.htm |year=1997 |url-status=dead |archive-url=https://web.archive.org/web/20060112115812/http://www.concentric.net/~Ttwang/tech/sorthash.htm |archive-date=2006-01-12 }}</ref> नियतात्मक रूप से आदेशित सेट प्रदान करने के लिए उपयोग किया जा सकता है। | ||
इसके अतिरिक्त, उन भाषाओं में जो नक्शों का समर्थन करती हैं किन्तु | इसके अतिरिक्त, उन भाषाओं में जो नक्शों का समर्थन करती हैं किन्तु सेट का नहीं, सेट को नक्शों के संदर्भ में प्रारम्भ किया जा सकता है। उदाहरण के लिए, [[पर्ल]] में सामान्य [[प्रोग्रामिंग मुहावरा]] जो सरणी को मिश्रण में परिवर्तित करता है जिसका मूल्य प्रहरी मान 1 है। सेट के रूप में उपयोग के लिए: | ||
<syntaxhighlight lang="perl"> | <syntaxhighlight lang="perl"> | ||
my %elements = map { $_ => 1 } @elements; | my %elements = map { $_ => 1 } @elements; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
अन्य लोकप्रिय विधियों में [[सरणी डेटा संरचना]] सम्मिलित है। विशेष रूप से पूर्णांक 1..n का | अन्य लोकप्रिय विधियों में [[सरणी डेटा संरचना]] सम्मिलित है। विशेष रूप से पूर्णांक 1..n का सेट n- [[बिट सरणी]] के रूप में कुशलतापूर्वक कार्यान्वित किया जा सकता है, जो अधिक ही कुशल संघ एवं चौराहे के संचालन का भी समर्थन करता है।[[ ब्लूम नक्शा ]] अधिक ही ठोस प्रतिनिधित्व का उपयोग करते हुए संभावित रूप से सेट को प्रारम्भ करता है, किन्तु प्रश्नों पर झूठी सकारात्मकता की अल्प संभावना को संकट में डालता है। | ||
बूलियन | बूलियन सेट संचालनों को अधिक प्राथमिक संचालनों के संदर्भ में कार्यान्वित किया जा सकता है (<code>pop</code>, <code>clear</code>, एवं <code>add</code>), किन्तु विशेष एल्गोरिदम अर्घ्य स्पर्शोन्मुख समय सीमा उत्पन्न कर सकते हैं। यदि सेट को क्रम की गई सूचियों के रूप में कार्यान्वित किया जाता है, उदाहरण के लिए, भोली एल्गोरिथ्म के लिए <code>union(''S'',''T'')</code> S की लंबाई m गुणा T की लंबाई n के अनुपात में समय लगेगा, जबकि [[मर्ज एल्गोरिथम]] का संस्करण m+n के आनुपातिक समय में कार्य करेगा। इसके अतिरिक्त, विशेष सेट डेटा संरचनाएं हैं (जैसे कि [[ संघ-खोज एल्गोरिथ्म |संघ-शोध एल्गोरिथ्म]] ) जो दूसरों के मूल्य पर इनमें से अधिक संचालन के लिए अनुकूलित हैं। | ||
== भाषा समर्थन == | == भाषा समर्थन == | ||
[[ पास्कल प्रोग्रामिंग भाषा ]] | [[ पास्कल प्रोग्रामिंग भाषा ]] सेट का समर्थन करने वाली प्रारंभिक भाषाओं में से थी; कई भाषाओं में अब यह सम्मिलित है, मूल भाषा में हो या किसी [[मानक पुस्तकालय]] में होता है। | ||
* [[C++]] में, [[मानक टेम्पलेट लाइब्रेरी|मानक टेम्पलेट पुस्तकालय]] (STL) प्रदान करती है <code>[[set (C++)|set]]</code> टेम्प्लेट कक्ष, जिसे सामान्यतः बाइनरी सर्च ट्री (जैसे लाल-काले पेड़) का उपयोग करके प्रारम्भ किया जाता है; [[सिलिकॉन ग्राफिक्स इंटरनेशनल]] का एसटीएल भी प्रदान करता है <code>hash_set</code> टेम्प्लेट कक्ष, जो मिश्रण तालिका का उपयोग करके एक | * [[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> प्रकार करता है। | * रस्ट (प्रोग्रामिंग भाषा) मानक पुस्तकालय सामान्य प्रदान <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|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 (प्रोग्रामिंग भाषा)]] में उपयोग करते है। | * ऐप्पल इंक की [[फाउंडेशन किट]] ([[कोको (एपीआई)]] का भाग) [[ उद्देश्य सी | उद्देश्य 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 के पश्चात से, कर्ली-ब्रैकेट सिंटैक्स का उपयोग करके गैर-रिक्त | * [[पायथन (प्रोग्रामिंग भाषा)]] में अंतर्निहित है [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> रिक्त शब्दकोश का प्रतिनिधित्व करने के लिए करता है। | ||
* .NET फ्रेमवर्क जेनेरिक प्रदान करता है <code>[http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet]</code> एवं <code>[http://msdn.microsoft.com/en-us/library/dd412070.aspx SortedSet]</code> कक्षाएं जो सामान्य <code>[http://msdn.microsoft.com/en-us/library/dd412081.aspx ISet] अंतराफलक</code>को प्रारम्भ करती हैं। | * .NET फ्रेमवर्क जेनेरिक प्रदान करता है <code>[http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet]</code> एवं <code>[http://msdn.microsoft.com/en-us/library/dd412070.aspx SortedSet]</code> कक्षाएं जो सामान्य <code>[http://msdn.microsoft.com/en-us/library/dd412081.aspx ISet] अंतराफलक</code>को प्रारम्भ करती हैं। | ||
* स्मॉलटॉक की कक्ष पुस्तकालय में सम्मिलित हैं <code>Set</code> एवं <code>IdentitySet</code>समावेशन परीक्षण के लिए क्रमशः समानता एवं पहचान का उपयोग करना, कई बोलियाँ संपीडित भंडारण के लिए भिन्नताएँ प्रदान करती हैं (<code>NumberSet</code>, <code>CharacterSet</code>), ऑर्डर करने के लिए (<code>OrderedSet</code>, <code>SortedSet</code>, आदि) या [[कमजोर संदर्भ|शक्तिहीन संदर्भ (<code>WeakIdentitySet</code>)]] के लिए होता है । | * स्मॉलटॉक की कक्ष पुस्तकालय में सम्मिलित हैं <code>Set</code> एवं <code>IdentitySet</code>समावेशन परीक्षण के लिए क्रमशः समानता एवं पहचान का उपयोग करना, कई बोलियाँ संपीडित भंडारण के लिए भिन्नताएँ प्रदान करती हैं (<code>NumberSet</code>, <code>CharacterSet</code>), ऑर्डर करने के लिए (<code>OrderedSet</code>, <code>SortedSet</code>, आदि) या [[कमजोर संदर्भ|शक्तिहीन संदर्भ (<code>WeakIdentitySet</code>)]] के लिए होता है । | ||
* [[रूबी (प्रोग्रामिंग भाषा)]] के मानक पुस्तकालय में a <code>[http://ruby-doc.org/stdlib/libdoc/set/rdoc/index.html set]</code> सम्मिलित है, <code>Set</code> एवं <code>SortedSet</code>मॉड्यूल जिसमें सम्मिलित है कक्षाएं जो मिश्रण तालिका का उपयोग करके | * [[रूबी (प्रोग्रामिंग भाषा)]] के मानक पुस्तकालय में a <code>[http://ruby-doc.org/stdlib/libdoc/set/rdoc/index.html set]</code> सम्मिलित है, <code>Set</code> एवं <code>SortedSet</code>मॉड्यूल जिसमें सम्मिलित है कक्षाएं जो मिश्रण तालिका का उपयोग करके सेट को प्रारम्भ करती हैं, पश्चात वाले क्रमबद्ध क्रम में पुनरावृत्ति की अनुमति देते हैं। | ||
* [[OCaml]] की मानक पुस्तकालय में a सम्मिलित होता है, <code>Set</code> मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके कार्यात्मक | * [[OCaml]] की मानक पुस्तकालय में a सम्मिलित होता है, <code>Set</code> मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके कार्यात्मक सेट डेटा संरचना को प्रारम्भ करता है। | ||
* [[हास्केल (प्रोग्रामिंग भाषा)]] का [[ग्लासगो हास्केल कंपाइलर]] कार्यान्वयन प्रदान करता है <code>[https://hackage.haskell.org/package/containers/docs/Data-Set.html Data.Set]</code> मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके अपरिवर्तनीय | * [[हास्केल (प्रोग्रामिंग भाषा)]] का [[ग्लासगो हास्केल कंपाइलर]] कार्यान्वयन प्रदान करता है <code>[https://hackage.haskell.org/package/containers/docs/Data-Set.html Data.Set]</code> मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके अपरिवर्तनीय सेट को प्रारम्भ करता है।<ref>Stephen Adams, [http://www.swiss.ai.mit.edu/~adams/BB "''Efficient sets: a balancing act''"], Journal of Functional Programming 3(4):553-562, October 1993. Retrieved on 2015-03-11.</ref> | ||
* [[Tcl]] [[Tcllib]] पैकेज | * [[Tcl]] [[Tcllib]] पैकेज सेट मॉड्यूल प्रदान करता है जो TCL सूचियों के आधार पर सेट डेटा संरचना को प्रारम्भ करता है। | ||
* [[ स्विफ्ट (प्रोग्रामिंग भाषा) | स्विफ्ट (प्रोग्रामिंग भाषा) a]] <code>Set</code> प्रकार, स्विफ्ट 1.2 के पश्चात से।स्टैंडर्ड पुस्तकालय में होता है। | * [[ स्विफ्ट (प्रोग्रामिंग भाषा) | स्विफ्ट (प्रोग्रामिंग भाषा) a]] <code>Set</code> प्रकार, स्विफ्ट 1.2 के पश्चात से।स्टैंडर्ड पुस्तकालय में होता है। | ||
* [[जावास्क्रिप्ट]] <code>[https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set Set]</code> ईसीएमएस्क्रिप्ट 2015 के साथ मानक अंतर्निर्मित वस्तु के रूप में प्रस्तुत किया <ref>{{Cite web|url=http://www.ecma-international.org/ecma-262/6.0/#sec-set-objects|title=ECMAScript 2015 Language Specification – ECMA-262 6th Edition|website=www.ecma-international.org|language=en-GB|access-date=2017-07-11}}</ref> है। | * [[जावास्क्रिप्ट]] <code>[https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set Set]</code> ईसीएमएस्क्रिप्ट 2015 के साथ मानक अंतर्निर्मित वस्तु के रूप में प्रस्तुत किया <ref>{{Cite web|url=http://www.ecma-international.org/ecma-262/6.0/#sec-set-objects|title=ECMAScript 2015 Language Specification – ECMA-262 6th Edition|website=www.ecma-international.org|language=en-GB|access-date=2017-07-11}}</ref> है। | ||
* [[Erlang (प्रोग्रामिंग भाषा)]] की मानक पुस्तकालय में a <code>[http://erlang.org/doc/man/sets.html sets]</code> मापांक होता है। | * [[Erlang (प्रोग्रामिंग भाषा)]] की मानक पुस्तकालय में a <code>[http://erlang.org/doc/man/sets.html sets]</code> मापांक होता है। | ||
* [[क्लोजर]] में मिश्रण | * [[क्लोजर]] में मिश्रण सेट के लिए शाब्दिक सिंटैक्स है, एवं सॉर्ट किए गए सेट को भी प्रारम्भ करता है। | ||
* [[LabVIEW]] के निकट संस्करण 2019 से | * [[LabVIEW]] के निकट संस्करण 2019 से सेट के लिए मूल समर्थन है। | ||
* [[एडा (प्रोग्रामिंग भाषा)]] <code>[http://www.ada-auth.org/standards/12rm/html/RM-A-18-8.html Ada.Containers.Hashed_Sets]</code> एवं <code>[http://www.ada-auth.org/standards/12rm/html/RM-A-18-9.html Ada.Containers.Ordered_Sets]</code> संकुल प्रदान करता है। | * [[एडा (प्रोग्रामिंग भाषा)]] <code>[http://www.ada-auth.org/standards/12rm/html/RM-A-18-8.html Ada.Containers.Hashed_Sets]</code> एवं <code>[http://www.ada-auth.org/standards/12rm/html/RM-A-18-9.html Ada.Containers.Ordered_Sets]</code> संकुल प्रदान करता है। | ||
जैसा कि पूर्व खंड में उल्लेख किया गया है, उन भाषाओं में जो साधारण | जैसा कि पूर्व खंड में उल्लेख किया गया है, उन भाषाओं में जो साधारण सेट का समर्थन नहीं करते हैं, किन्तु साहचर्य सरणियों का समर्थन करते हैं, तत्वों को कुंजियों के रूप में उपयोग करके, एवं मूल्यों के रूप में डमी मान का उपयोग करके सेट को साहचर्य सरणियों का उपयोग करके अनुकरण किया जा सकता है, जिन्हें अनदेखा किया जाता है। | ||
== बहुसमुच्चय == | == बहुसमुच्चय == | ||
{{Main|बहुसमुच्चय}} | {{Main|बहुसमुच्चय}} | ||
सेट की धारणा का सामान्यीकरण बहुसमुच्चय या बैग का है, जो सेट के समान है किन्तु बार-बार मान की अनुमति देता है। इसका उपयोग दो भिन्न-भिन्न अर्थों में किया जाता है: या तो समान मानों को समान माना जाता है एवं उन्हें केवल गिना जाता है, या समान मानों को समतुल्य माना जाता है एवं भिन्न-भिन्न वस्तुओं के रूप में संग्रहीत किया जाता है। उदाहरण के लिए, लोगों की सूची (नाम से) एवं उम्र (वर्षों में) दी गई है, कोई भी उम्र के बहुसमुच्चय का निर्माण कर सकता है, जो कि किसी दिए गए उम्र के लोगों की संख्या की गणना करता है। वैकल्पिक रूप से, कोई लोगों का बहुसमुच्चय बना सकता है, जहां दो लोगों को समान माना जाता है यदि उनकी आयु समान है (किन्तु भिन्न-भिन्न लोग हो सकते हैं एवं भिन्न-भिन्न नाम हो सकते हैं), इस विषय में प्रत्येक जोड़ी (नाम, आयु) को संग्रहित किया जाना चाहिए, एवं चयन करना दी गई आयु पर दी गई आयु के सभी लोगों को देता है। | |||
औपचारिक रूप से, कंप्यूटर विज्ञान में वस्तुओं के लिए कुछ [[तुल्यता संबंध]] के अनुसार समान माना जाना संभव है किन्तु अन्य संबंध के अनुसार भिन्न है। कुछ प्रकार के बहुसमुच्चय कार्यान्वयन भिन्न-भिन्न समान वस्तुओं को डेटा संरचना में भिन्न-भिन्न वस्तुओं के रूप में संग्रहीत करेंगे; जबकि अन्य इसे संस्करण में संक्षिप्त कर देंगे एवं तत्व की बहुलता की सकारात्मक पूर्णांक गणना रखेंगे। | औपचारिक रूप से, कंप्यूटर विज्ञान में वस्तुओं के लिए कुछ [[तुल्यता संबंध]] के अनुसार समान माना जाना संभव है किन्तु अन्य संबंध के अनुसार भिन्न है। कुछ प्रकार के बहुसमुच्चय कार्यान्वयन भिन्न-भिन्न समान वस्तुओं को डेटा संरचना में भिन्न-भिन्न वस्तुओं के रूप में संग्रहीत करेंगे; जबकि अन्य इसे संस्करण में संक्षिप्त कर देंगे एवं तत्व की बहुलता की सकारात्मक पूर्णांक गणना रखेंगे। | ||
सेट के साथ, बहुसमुच्चय स्वाभाविक रूप से मिश्रण तालिका या पेड़ों का उपयोग करके कार्यान्वित किया जा सकता है, जो विभिन्न प्रदर्शन विशेषताओं को उत्पन्न करता है। | |||
टाइप टी पर सभी बैग का | टाइप टी पर सभी बैग का सेट अभिव्यक्ति बैग टी द्वारा दिया गया है। यदि बहुसमुच्चय द्वारा कोई समान वस्तुओं को समान मानता है एवं उन्हें सरलता से गिनता है, तो बहुसमुच्चय को इनपुट डोमेन से गैर-नकारात्मक पूर्णांक (प्राकृतिक) के फ़ंक्शन के रूप में व्याख्या किया जा सकता है संख्या), इसके सूचक समारोह के साथ सेट की पहचान को सामान्यीकृत करना, कुछ स्थितियों में इस गिनती के अर्थ में बहुसमुच्चय को नकारात्मक मूल्यों की अनुमति देने के लिए सामान्यीकृत किया जा सकता है, जैसा कि पायथन में है। | ||
* C++ की मानक टेम्पलेट पुस्तकालय चयन किए गए एवं अवर्गीकृत बहुसमुच्चय दोनों को प्रारम्भ करती है। यह <code>[[Multiset (C++)|multiset]]</code> क्रमबद्ध बहुसमुच्चय के लिए कक्ष प्रदान करता है, [[सहयोगी कंटेनर (सी ++)|सहयोगी कंटेनर (C ++)]] के रूप में, जो स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करके इस बहुसमुच्चय को प्रारम्भ करता है। यह <code>unordered_multiset</code> [[अनियंत्रित सहयोगी कंटेनर (सी ++)|अनियंत्रित सहयोगी कंटेनर (C ++)]]C++) के रूप में अवर्गीकृत बहुसमुच्चय के लिए कक्ष प्रदान करता है, जो मिश्रण तालिका का उपयोग करके इस बहुसमुच्चय को प्रारम्भ करता है। अवर्गीकृत बहुसमुच्चय C++11 के अनुसार मानक है; प्रथम SGI का STL प्रदान करता है <code>hash_multiset</code> कक्ष, जिसे कॉपी किया गया एवं अंततः मानकीकृत किया गया। | * C++ की मानक टेम्पलेट पुस्तकालय चयन किए गए एवं अवर्गीकृत बहुसमुच्चय दोनों को प्रारम्भ करती है। यह <code>[[Multiset (C++)|multiset]]</code> क्रमबद्ध बहुसमुच्चय के लिए कक्ष प्रदान करता है, [[सहयोगी कंटेनर (सी ++)|सहयोगी कंटेनर (C ++)]] के रूप में, जो स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करके इस बहुसमुच्चय को प्रारम्भ करता है। यह <code>unordered_multiset</code> [[अनियंत्रित सहयोगी कंटेनर (सी ++)|अनियंत्रित सहयोगी कंटेनर (C ++)]]C++) के रूप में अवर्गीकृत बहुसमुच्चय के लिए कक्ष प्रदान करता है, जो मिश्रण तालिका का उपयोग करके इस बहुसमुच्चय को प्रारम्भ करता है। अवर्गीकृत बहुसमुच्चय C++11 के अनुसार मानक है; प्रथम SGI का STL प्रदान करता है <code>hash_multiset</code> कक्ष, जिसे कॉपी किया गया एवं अंततः मानकीकृत किया गया। | ||
Line 119: | Line 119: | ||
* स्मॉलटाक में <code>Bag</code>सम्मिलित हैं,वर्ग जिसे समावेशन परीक्षण के लिए विधेय के रूप में या तो पहचान या समानता का उपयोग करने के लिए तत्काल किया जा सकता है। | * स्मॉलटाक में <code>Bag</code>सम्मिलित हैं,वर्ग जिसे समावेशन परीक्षण के लिए विधेय के रूप में या तो पहचान या समानता का उपयोग करने के लिए तत्काल किया जा सकता है। | ||
जहां बहुसमुच्चय डेटा संरचना उपलब्ध नहीं है, नियमित | जहां बहुसमुच्चय डेटा संरचना उपलब्ध नहीं है, नियमित सेट का उपयोग करने के लिए वर्कअराउंड है, किन्तु भिन्न-भिन्न वस्तुओं पर सदैव समान नहीं होने के लिए समानता की भविष्यवाणी को ओवरराइड करता है (चूंकि, यह अभी भी उसी की कई घटनाओं को एकत्र करने में सक्षम नहीं होगा ) या उनके पूर्णांक गुणकों के मानों को मैप करने के लिए साहचर्य सरणी का उपयोग करें (यह समान तत्वों के बीच अंतर करने में सक्षम नहीं होगा)। | ||
बैग पर विशिष्ट संचालन: | बैग पर विशिष्ट संचालन: | ||
Line 128: | Line 128: | ||
* <code>union(''B''<sub>1</sub>, ''B''<sub>2</sub>)</code>: बैग ''B''<sub>1</sub> या ''B''<sub>2</sub> देता है,जिसमें केवल वे मान होते हैं, में होने वाले केवल उन मानों वाले बैग को लौटाता है, इसके कि परिणामी बैग में मान x की संख्या समान होती है (''B''<sub>1</sub> # x) + (''B''<sub>2</sub> # x), कभी-कभी B1 ⊎ B2 के रूप में निरूपित किया जाता है | * <code>union(''B''<sub>1</sub>, ''B''<sub>2</sub>)</code>: बैग ''B''<sub>1</sub> या ''B''<sub>2</sub> देता है,जिसमें केवल वे मान होते हैं, में होने वाले केवल उन मानों वाले बैग को लौटाता है, इसके कि परिणामी बैग में मान x की संख्या समान होती है (''B''<sub>1</sub> # x) + (''B''<sub>2</sub> # x), कभी-कभी B1 ⊎ B2 के रूप में निरूपित किया जाता है | ||
SQL बहुसमुच्चय [[संबंधपरक डेटाबेस प्रबंधन प्रणाली]] में, तालिका (गणितीय) | SQL बहुसमुच्चय [[संबंधपरक डेटाबेस प्रबंधन प्रणाली]] में, तालिका (गणितीय) सेट या बहुसमुच्चय हो सकती है, जो कुछ स्तंभों पर एकता की कमी की उपस्थिति पर निर्भर करता है। | ||
[[एसक्यूएल]] संबंधित तालिका से पंक्तियों के चयन की अनुमति देता है: यह संचालन सामान्य रूप से बहुसमुच्चय उत्पन्न करेगा, जब तक कि कीवर्ड <code>DISTINCT</code> पंक्तियों को सभी भिन्न-भिन्न होने के लिए विवश करने के लिए प्रयोग किया जाता है, या चयन में प्राथमिक कुंजी सम्मिलित होती है। | [[एसक्यूएल]] संबंधित तालिका से पंक्तियों के चयन की अनुमति देता है: यह संचालन सामान्य रूप से बहुसमुच्चय उत्पन्न करेगा, जब तक कि कीवर्ड <code>DISTINCT</code> पंक्तियों को सभी भिन्न-भिन्न होने के लिए विवश करने के लिए प्रयोग किया जाता है, या चयन में प्राथमिक कुंजी सम्मिलित होती है। | ||
Line 142: | Line 142: | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[ब्लूम फिल्टर]] | * [[ब्लूम फिल्टर]] | ||
* [[विसंधित सेट | * [[विसंधित सेट (डेटा संरचना)]] | ||
* [[सेट | * [[सेट (गणित)]] | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== |
Revision as of 15:24, 27 May 2023
भारत कंप्यूटर विज्ञान, सेट सार डेटा प्रकार है जो बिना किसी विशेष क्रम के अद्वितीय मूल्यों को संग्रहीत कर सकता है। यह परिमित समुच्चय की गणित अवधारणा का कंप्यूटर कार्यान्वयन है। अधिकांश अन्य संग्रह (सार डेटा प्रकार) प्रकारों के विपरीत, सेट से विशिष्ट तत्व को पुनः प्राप्त करने के अतिरिक्त, सामान्यतः सेट में सदस्यता के लिए मूल्य का परीक्षण किया जाता है।
कुछ सेट डेटा संरचनाएं स्थिर या एकत्रित सेट के लिए चित्रित किए गए हैं जो उनके निर्माण के पश्चात परिवर्तित नहीं होते हैं। स्थिर सेट स्वयं तत्वों पर केवल क्वेरी संचालन की अनुमति देते हैं - जैसे कि यह देखना कि क्या दिया गया मान सेट में है, या कुछ मनमाना क्रम में मानों की गणना करना अन्य वेरिएंट, जिन्हें डायनेमिक या म्यूतालिका सेट कहा जाता है, सेट से तत्वों को सम्मिलित करने एवं विस्थापित करने की भी अनुमति देते हैं।
बहुसमुच्चय विशेष प्रकार का सेट है, जिसमें तत्व सेट में कई बार दिखाई दे सकता है।
प्रकार सिद्धांत
प्रकार सिद्धांत में, सेट सामान्यतः उनके संकेतक फ़ंक्शन (विशेषता समारोह) के साथ पहचाने जाते हैं: तदनुसार, प्रकार के मूल्यों का सेट या द्वारा दर्शाया जा सकता है। (उपप्रकार एवं सेट को शोधन प्रकार द्वारा प्रतिरूपित किया जा सकता है, एवं भागफल सेट को परिवर्तनीय सेट द्वारा प्रतिस्थापित किया जा सकता है।) विशेषता कार्य सेट को परिभाषित किया जाता है।
सिद्धांत रूप में, कई अन्य अमूर्त डेटा संरचनाओं को मानक संचालन पर लगाए गए अतिरिक्त संचालन एवंअतिरिक्त सिद्धांतों के साथ सेट संरचनाओं के रूप में देखा जा सकता है। उदाहरण के लिए, अमूर्त हीप डेटा संरचना को सेट संरचना के रूप में देखा जा सकता है 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(x1,x2,…,xn,)
: मान x के साथ x1,x2,...,xn सेट संरचना बनाता है।create_from(collection)
: दिए गए संग्रह के सभी तत्वों (सार डेटा प्रकार) या दिए गए पुनरावर्तक द्वारा लौटाए गए सभी तत्वों वाली नई सेट संरचना बनाता है।
गतिशील सेट
गतिशील सेट संरचनाएं सामान्यतः जोड़ती हैं,
create()
: प्रारंभ में रिक्त सेट संरचना बनाता है।create_with_capacity(n)
: नई सेट संरचना बनाता है, प्रारंभ में रिक्त किन्तु n तत्वों तक धारण करने में सक्षम होते है।
add(S,x)
: तत्व x को S में जोड़ता है, यदि यह पहले से उपस्थित नहीं है।remove(S, x)
: तत्व x को S से विस्थापित करता है, यदि यह उपस्थित है।capacity(S)
: S द्वारा धारण किए जा सकने वाले मानों की अधिकतम संख्या लौटाता है।
कुछ सेट संरचनाएं इनमें से केवल कुछ परिचालनों की अनुमति दे सकती हैं। प्रत्येक संचालन के वित्त कार्यान्वयन पर निर्भर करेगी, एवं संभवतः सेट में संग्रहीत विशेष मूल्यों पर भी, एवं जिस क्रम में उन्हें सम्मिलित किया गया है।
अतिरिक्त संचालन
ऐसे कई अन्य संचालन हैं जिन्हें (सिद्धांत रूप में) उपरोक्त के संदर्भ में परिभाषित किया जा सकता है, जैसे:
pop(S)
: S का एक मनमाना तत्व लौटाता है, इसे 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)
: s के सभी तत्वों से युक्त सबसेट लौटाता है जो किसी दिए गए विधेय (गणितीय तर्क) p को संतुष्ट करता है।fold(A0,F,S)
: मान A|S| लौटाता है, आवेदन करने के पश्चातAi+1 := F(Ai, e)
S के प्रत्येक तत्व ई के लिए, कुछ बाइनरी संचालन F के लिए F को अच्छी प्रकार से परिभाषित करने के लिए सहयोगी एवं कम्यूटेटिव होना चाहिए।clear(S)
: s के सभी तत्वों को विस्थापित कर दें।equal(S1', S2')
: जांचता है कि क्या दिए गए दो सेट समान हैं (अर्थात सभी एवं केवल समान तत्व सम्मिलित हैं)।hash(S)
: स्थिर सेट S के लिए मिश्रण मान लौटाता है जैसे कि ifequal(S1, S2)
तबhash(S1) = hash(S2) है।
अन्य कार्यों को विशेष प्रकार के तत्वों वाले सेट के लिए परिभाषित किया जा सकता है:
sum(S)
: योग की कुछ परिभाषा के लिए S के सभी तत्वों का योग लौटाता है। उदाहरण के लिए, पूर्णांक या वास्तविक से अधिक, इसेfold(0, add, S)
इस रूप में परिभाषित किया जा सकता है।collapse(S)
: सेट काsum
सेट दिया गया है, संघ वापस करें,[6] उदाहरण के लिए,collapse({{1}, {2, 3}}) == {1, 2, 3}
. प्रकार का माना जा सकता है।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)
: शोधन करता है कि बैग B में तत्व X उपस्थित है।is_sub_bag(B1, B2)
: शोधन करता है कि बैग B1 में प्रत्येक तत्व है या B1 में नहीं होता है, बैग B2 में होने की तुलना में अधिक बार नहीं; कभी-कभी B1 ⊑ B2 के रूप में दर्शाया जाता है।count(B, x)
: तत्व x के बैग B में होने की संख्या लौटाता है; कभी-कभी B # x के रूप में दर्शाया जाता है।scaled_by(B, n)
: प्राकृतिक संख्या n दिया गया है, जिसमें बैग B के समान तत्व होते हैं, प्रत्येक तत्व जो B में M बार होता है परिणामी बैग में n * m बार होता है; कभी-कभी n ⊗ B के रूप में निरूपित किया जाता है।union(B1, B2)
: बैग B1 या B2 देता है,जिसमें केवल वे मान होते हैं, में होने वाले केवल उन मानों वाले बैग को लौटाता है, इसके कि परिणामी बैग में मान x की संख्या समान होती है (B1 # x) + (B2 # x), कभी-कभी B1 ⊎ B2 के रूप में निरूपित किया जाता है
SQL बहुसमुच्चय संबंधपरक डेटाबेस प्रबंधन प्रणाली में, तालिका (गणितीय) सेट या बहुसमुच्चय हो सकती है, जो कुछ स्तंभों पर एकता की कमी की उपस्थिति पर निर्भर करता है।
एसक्यूएल संबंधित तालिका से पंक्तियों के चयन की अनुमति देता है: यह संचालन सामान्य रूप से बहुसमुच्चय उत्पन्न करेगा, जब तक कि कीवर्ड DISTINCT
पंक्तियों को सभी भिन्न-भिन्न होने के लिए विवश करने के लिए प्रयोग किया जाता है, या चयन में प्राथमिक कुंजी सम्मिलित होती है।
एसक्यूएल मानकीकरण इतिहास में MULTISET
उप-क्वेरी को संग्रह अभिव्यक्ति में परिवर्तित करने के लिए कीवर्ड का उपयोग किया जा सकता है।
SELECT expression1, expression2... FROM table_name...
सामान्य चयन है, जिसका उपयोग किसी अन्य सामान्य क्वेरी की सबक्वेरी अभिव्यक्ति के रूप में किया जा सकता है, जबकि
MULTISET(SELECT expression1, expression2... FROM table_name...)
सबक्वायरी को संग्रह अभिव्यक्ति में परिवर्तित कर देता है जिसका उपयोग किसी अन्य क्वेरी में या उचित संग्रह प्रकार के कॉलम में कार्यभार में किया जा सकता है।
यह भी देखें
टिप्पणियाँ
संदर्भ
- ↑ 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.