क्या नेट के लिए मल्टीसेट का कोई कार्यान्वयन है?

Question

मैं एक मल्टीसेट के .NET कार्यान्वयन की तलाश में हूं। क्या कोई अच्छाई सुझा सकता है?

(एक मल्टीसेट, या बैग, एक सेट है जिसमें डुप्लिकेट मान हो सकते हैं, और जिस पर आप सेट ऑपरेशंस कर सकते हैं: चौराहे, अंतर इत्यादि। उदाहरण के लिए एक शॉपिंग कार्ट को मल्टीसेट के रूप में माना जा सकता है क्योंकि आप कर सकते हैं एक ही उत्पाद की कई घटनाएं हैं।)

Answer 1

मुझे एक के बारे में पता नहीं है, हालांकि आप उस के लिए Dictionary का उपयोग कर सकते हैं, जिसमें मूल्य आइटम की मात्रा है। और जब आइटम दूसरी बार जोड़ा जाता है, तो आप शब्दकोश में इसके लिए मूल्य बढ़ा सकते हैं।

अन्य संभावनाओं का उपयोग केवल List आइटमों का उपयोग करना होगा, जिसमें आप डुप्लिकेट डाल सकते हैं। यह एक शॉपिंग कार्ट के लिए एक बेहतर तरीका हो सकता है।

Answer 2

public class Multiset<T>: ICollection<T> 
{ 
    private readonly Dictionary<T, int> data; 

    public Multiset() 
    { 
     data = new Dictionary<T, int>(); 
    } 

    private Multiset(Dictionary<T, int> data) 
    { 
     this.data = data; 
    } 

    public void Add(T item) 
    { 
     int count = 0; 
     data.TryGetValue(item, out count); 
     count++; 
     data[item] = count; 
    } 

    public void Clear() 
    { 
     data.Clear(); 
    } 

    public Multiset<T> Except(Multiset<T> another) 
    { 
     Multiset<T> copy = new Multiset<T>(new Dictionary<T, int>(data)); 
     foreach (KeyValuePair<T, int> kvp in another.data) 
     { 
      int count; 
      if (copy.data.TryGetValue(kvp.Key, out count)) 
      { 
       if (count > kvp.Value) 
       { 
        copy.data[kvp.Key] = count - kvp.Value; 
       } 
       else 
       { 
        copy.data.Remove(kvp.Key); 
       } 
      } 
     } 
     return copy; 
    } 

    public Multiset<T> Intersection(Multiset<T> another) 
    { 
     Dictionary<T, int> newData = new Dictionary<T, int>(); 
     foreach (T t in data.Keys.Intersect(another.data.Keys)) 
     { 
      newData[t] = Math.Min(data[t], another.data[t]); 
     } 
     return new Multiset<T>(newData); 
    } 

    public bool Contains(T item) 
    { 
     return data.ContainsKey(item); 
    } 

    public void CopyTo(T[] array, int arrayIndex) 
    { 
     foreach (KeyValuePair<T, int> kvp in data) 
     { 
      for (int i = 0; i < kvp.Value; i++) 
      { 
       array[arrayIndex] = kvp.Key; 
       arrayIndex++; 
      } 
     } 
    } 

    public IEnumerable<T> Mode() 
    { 
     if (!data.Any()) 
     { 
      return Enumerable.Empty<T>(); 
     } 
     int modalFrequency = data.Values.Max(); 
     return data.Where(kvp => kvp.Value == modalFrequency).Select(kvp => kvp.Key); 
    } 

    public int Count 
    { 
     get 
     { 
      return data.Values.Sum(); 
     } 
    } 

    public bool IsReadOnly 
    { 
     get 
     { 
      return false; 
     } 
    } 

    public bool Remove(T item) 
    { 
     int count; 
     if (!data.TryGetValue(item, out count)) 
     { 
      return false; 
     } 
     count--; 
     if (count == 0) 
     { 
      data.Remove(item); 
     } 
     else 
     { 
      data[item] = count; 
     } 
     return true; 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return new MultisetEnumerator<T>(this); 
    } 

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    { 
     return new MultisetEnumerator<T>(this); 
    } 

    private class MultisetEnumerator<T> : IEnumerator<T> 
    { 
     public MultisetEnumerator(Multiset<T> multiset) 
     { 
      this.multiset = multiset; 
      baseEnumerator = multiset.data.GetEnumerator(); 
      index = 0; 
     } 

     private readonly Multiset<T> multiset; 
     private readonly IEnumerator<KeyValuePair<T, int>> baseEnumerator; 
     private int index; 

     public T Current 
     { 
      get 
      { 
       return baseEnumerator.Current.Key; 
      } 
     } 

     public void Dispose() 
     { 
      baseEnumerator.Dispose(); 
     } 

     object System.Collections.IEnumerator.Current 
     { 
      get 
      { 
       return baseEnumerator.Current.Key; 
      } 
     } 

     public bool MoveNext() 
     { 
      KeyValuePair<T, int> kvp = baseEnumerator.Current; 
      if (index < (kvp.Value - 1)) 
      { 
       index++; 
       return true; 
      } 
      else 
      { 
       bool result = baseEnumerator.MoveNext(); 
       index = 0; 
       return result; 
      } 
     } 

     public void Reset() 
     { 
      baseEnumerator.Reset(); 
     } 
    } 
} 

Answer 3

किसी भी चीज को स्वयं को मल्टीसेट के सी # कार्यान्वयन को कॉल करना आंतरिक रूप से एक शब्दकोश पर आधारित नहीं होना चाहिए। शब्दकोश हैश टेबल, अनियंत्रित संग्रह हैं। सी ++ के सेट, मल्टीसेट, मानचित्र, और मल्टीमैप्स का ऑर्डर किया जाता है। आंतरिक रूप से प्रत्येक को आत्म-संतुलित बाइनरी खोज पेड़ के कुछ स्वाद के रूप में दर्शाया जाता है।

सी # में हमें हमारे कार्यान्वयन के आधार के रूप में सॉर्टेड डिक्शनरी का उपयोग करना चाहिए जैसा कि माइक्रोसॉफ्ट के अपने दस्तावेज के अनुसार एक सॉर्टेड डिक्शनरी "is a binary search tree with O(log n) retrieval" है।

public class SortedMultiSet<T> : IEnumerable<T> 
{ 
    private SortedDictionary<T, int> _dict; 

    public SortedMultiSet() 
    { 
     _dict = new SortedDictionary<T, int>(); 
    } 

    public SortedMultiSet(IEnumerable<T> items) : this() 
    { 
     Add(items); 
    } 

    public bool Contains(T item) 
    { 
     return _dict.ContainsKey(item); 
    } 

    public void Add(T item) 
    { 
     if (_dict.ContainsKey(item)) 
      _dict[item]++; 
     else 
      _dict[item] = 1; 
    } 

    public void Add(IEnumerable<T> items) 
    { 
     foreach (var item in items) 
      Add(item); 
    } 

    public void Remove(T item) 
    { 
     if (!_dict.ContainsKey(item)) 
      throw new ArgumentException(); 
     if (--_dict[item] == 0) 
      _dict.Remove(item); 
    } 

    // Return the last value in the multiset 
    public T Peek() 
    { 
     if (!_dict.Any()) 
      throw new NullReferenceException(); 
     return _dict.Last().Key; 
    } 

    // Return the last value in the multiset and remove it. 
    public T Pop() 
    { 
     T item = Peek(); 
     Remove(item); 
     return item; 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     foreach(var kvp in _dict) 
      for(int i = 0; i < kvp.Value; i++) 
       yield return kvp.Key; 
    } 

    IEnumerator IEnumerable.GetEnumerator() 
    { 
     return this.GetEnumerator(); 
    } 
}