title: Fastest way to find unique combinations of list
body: <p>I'm trying to solve the general problem of getting the unique combinations from a list in <code>Python</code></p>
  
  <p>Mathematically from <a href="https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html" rel="noreferrer">https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html</a> I can see that the formula for the number of combinations is <code>n!/r!(n-r)!</code> where <code>n</code> is the length of the sequence and <code>r</code> is the number to choose. </p>
  
  <p>As shown by the following python where <code>n</code> is 4 and <code>r</code> is 2:</p>
  
  <pre><code>lst = 'ABCD'
  result = list(itertools.combinations(lst, len(lst)/2))
  print len(result)
  6
  </code></pre>
  
  <p>The following is a helper function to show the issue I have:</p>
  
  <pre><code>def C(lst):
      l = list(itertools.combinations(sorted(lst), len(lst)/2))
      s = set(l)
      print 'actual', len(l), l
      print 'unique', len(s), list(s)
  </code></pre>
  
  <p>If I run this from iPython I can call it thus:</p>
  
  <pre><code>In [41]: C('ABCD')
  actual 6 [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]
  unique 6 [('B', 'C'), ('C', 'D'), ('A', 'D'), ('A', 'B'), ('A', 'C'), ('B', 'D')]
  
  In [42]: C('ABAB')
  actual 6 [('A', 'A'), ('A', 'B'), ('A', 'B'), ('A', 'B'), ('A', 'B'), ('B', 'B')]
  unique 3 [('A', 'B'), ('A', 'A'), ('B', 'B')]
  
  In [43]: C('ABBB')
  actual 6 [('A', 'B'), ('A', 'B'), ('A', 'B'), ('B', 'B'), ('B', 'B'), ('B', 'B')]
  unique 2 [('A', 'B'), ('B', 'B')]
  
  In [44]: C('AAAA')
  actual 6 [('A', 'A'), ('A', 'A'), ('A', 'A'), ('A', 'A'), ('A', 'A'), ('A', 'A')]
  unique 1 [('A', 'A')]
  </code></pre>
  
  <p>What I want to get is the unique count as shown above but doing a <code>combinations</code> and then <code>set</code> doesn't scale. 
  As when the length of <code>lst</code> which is <code>n</code> gets longer it slows down as the combinations get greater and greater. </p>
  
  <p>Is there a way of using math or <code>Python</code> tricks to to solve the issue of <strong>counting</strong> the unique combinations ?</p>