Iterate over all lists with one duplicate
<p>Consider all lists of length <code>n</code> where the values are integers from the <code>range 0 to n-1</code>. I would like to iterate as quickly as possible over every possible such list that has exactly one duplicate. If <code>n = 2</code> then the possible lists are:</p>

<pre><code>00
11
</code></pre>

<p>If <code>n = 3</code> they are:</p>

<pre><code>001
002
110
112
220
221
100
200
011
211
022
122
010
020
101
121
202
212
</code></pre>

<p>The total number of such lists is <code>n! * (n choose 2)</code> so I would like to avoid storing them all in memory if at all possible.</p>

<p>For each list I want to call a function that calculates a function of the list.<br>
What's a good way to do this?</p>

<p><strong>Benchmarks</strong> On my computer I get the following benchmark results</p>

<pre><code>timeit all(one_duplicate(6))
100 loops, best of 3: 6.87 ms per loops
timeit all(one_duplicate(7))
10 loops, best of 3: 59 ms per loop
timeit all(one_duplicate(8))
1 loops, best of 3: 690 ms per loop
timeit all(one_duplicate(9))
1 loops, best of 3: 7.58 s per loop
</code></pre>

<p>and</p>

<pre><code>timeit all(duplicates(range(6)))
10 loops, best of 3: 22.8 ms per loop
timeit all(duplicates(range(7)))
1 loops, best of 3: 416 ms per loop    
timeit all(duplicates(range(8)))
1 loops, best of 3: 9.78 s per loop
</code></pre>

<p>and</p>

<pre><code>timeit all(all_doublet_tuples(6))
100 loops, best of 3: 6.36 ms per loop
timeit all(all_doublet_tuples(7))
10 loops, best of 3: 60 ms per loop
timeit all(all_doublet_tuples(8))
1 loops, best of 3: 542 ms per loop
timeit all(all_doublet_tuples(9))
1 loops, best of 3: 7.27 s per loop
</code></pre>

<p>I declare <code>all_doublet_tuples</code> and <code>one_duplicate</code> to be equal first at the moment (allowing for noise in the tests).  </p>
