title: Why does Python's itertools.permutations contain duplicates? (When the original list has duplicates)
body: <p>It is universally agreed that a list of n <em>distinct</em> symbols has n! permutations. However, when the symbols are not distinct, the most common convention, in mathematics and elsewhere, seems to be to count only distinct permutations. Thus the permutations of the list <code>[1, 1, 2]</code> are usually considered to be<br>
  <code>[1, 1, 2], [1, 2, 1], [2, 1, 1]</code>. Indeed, the following C++ code prints precisely those three:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>int a[] = {1, 1, 2};
  do {
      cout&lt;&lt;a[0]&lt;&lt;" "&lt;&lt;a[1]&lt;&lt;" "&lt;&lt;a[2]&lt;&lt;endl;
  } while(next_permutation(a,a+3));
  </code></pre>
  
  <p>On the other hand, Python's <code>itertools.permutations</code> seems to print something else:</p>
  
  <pre class="lang-py prettyprint-override"><code>import itertools
  for a in itertools.permutations([1, 1, 2]):
      print a
  </code></pre>
  
  <p>This prints</p>
  
  <pre><code>(1, 1, 2)
  (1, 2, 1)
  (1, 1, 2)
  (1, 2, 1)
  (2, 1, 1)
  (2, 1, 1)
  </code></pre>
  
  <p>As user Artsiom Rudzenka pointed out in an answer, the <a href="http://docs.python.org/release/2.6.6/library/itertools.html?highlight=itertools#itertools.permutations" rel="noreferrer">Python documentation</a> says so:</p>
  
  <blockquote>
    <p>Elements are treated as unique based on their position, not on their value.</p>
  </blockquote>
  
  <p>My question: why was this design decision made? </p>
  
  <p>It seems that following the usual convention would give results that are more useful (and indeed it is usually exactly what I want)... or is there some application of Python's behaviour that I'm missing? </p>
  
  <p>[Or is it some implementation issue? The algorithm as in <code>next_permutation</code> — for instance explained on StackOverflow <a href="https://stackoverflow.com/questions/352203/generating-permutations-lazily/353248#353248">here (by me)</a> and <a href="https://stackoverflow.com/questions/4973077/the-amortized-complexity-of-stdnext-permutation">shown here to be O(1) amortised</a> — seems efficient and implementable in Python, but is Python doing something even more efficient since it doesn't guarantee lexicographic order based on value? And if so, was the increase in efficiency considered worth it?]</p>