Monday 19 September 2011

All possible subsets of set with duplicates removed

Given a set of character {a, b, c, d} find all subsets. The final list should not have any duplicate entry.



   1:  /// <summary>
   2:  /// Given set {a, b, c, d} below are all subsets 
   3:  ///     d
   4:  ///     dc     c     
   5:  ///     dca    cb     b   a
   6:  ///     dcba   cba    ba
   7:  ///     dca    ca
   8:  ///     db
   9:  ///     dba
  10:  ///     da
  11:  ///  This algortithm picks an item from input set and prepends it with items present in output set as well as adds the item
  12:  ///  This guarantees unordered combinations. i.e. it treats "ab" and "ba" same ways.
  13:  /// </summary>
  14:  /// <param name="data"></param>
  15:  /// <returns></returns>
  16:  static List<string> GetAllSubsets(char[] data)
  17:  {
  18:      List<string> result = new List<string>();
  19:      for (int i = 0; i < data.Length; i++)
  20:      {
  21:          for (int j = result.Count - 1; j >= 0; j--)
  22:          {
  23:              StringBuilder sb = new StringBuilder(result[j]);
  24:              sb.Insert(0, data[i]);
  25:              result.Add(sb.ToString());
  26:          }
  27:          result.Add(new string(new char[] { data[i] }));
  28:      }
  29:   
  30:      return result;
  31:  }

No comments:

Post a Comment