Czy są jakieś implementacje multiset dla .Net?

Question

Szukam wdrożenia .Net multiset. Czy ktoś może polecić dobry?

(Multiset lub torba, to zestaw, który może mieć zduplikowane wartości, i na którym można wykonać operacje zestawu: przecięcie, różnica itp. Na przykład koszyk może być traktowany jako multiset, ponieważ można mieć wiele wystąpień tego samego produktu.)

Answer 1

Nie wiem o jednym, jednak można użyć do tego celu wartości Dictionary, w której wartością jest ilość towaru. A gdy element zostanie dodany po raz drugi, możesz zwiększyć jego wartość w słowniku.

Inną możliwością byłoby po prostu użycie pozycji, w której można umieścić duplikaty. To może być lepsze podejście do koszyka na zakupy.

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

Wszystko, co nazywa się implementacją C# multiset, nie powinno opierać się na słownictwie wewnętrznie. Słowniki to tabele mieszania, kolekcje nieuporządkowane. Obsługiwane są zestawy CDE, multisety, mapy i multimapy. Wewnętrznie każdy jest reprezentowany jako pewien smak samowyważącego się binarnego drzewa wyszukiwania.

W języku C# powinniśmy użyć SortedDictionary jako podstawy naszej implementacji, zgodnie z własną dokumentacją Microsoftu a SortedDictionary "is a binary search tree with O(log n) retrieval". Podstawowym multiset mogą być realizowane w następujący sposób:

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(); 
    } 
}