Partitioning a sequence into sets of unique pairs
<p>I'm in need a of function which can split a sequence into pairs, and then combine them such that all elements in a combination is unique. I have tried a number of approaches using python's itertools, but have not found a solution.</p>

<p>To illustrate i would like a function which would take this sequence:
    [1, 2, 3, 4]</p>

<p>and split it into the following 3 combinations:</p>

<pre><code>[[1, 2], [3, 4]]
[[1, 3], [2, 4]]
[[1, 4], [2, 3]]
</code></pre>

<p>it should also work for longer sequences, but does not have to handle sequences of odd length. eg.</p>

<pre><code>[1,2,3,4,5,6]
</code></pre>

<p>splits into the following 15 combinations:</p>

<pre><code>[[1, 2], [3, 4], [5, 6]]
[[1, 2], [3, 5], [4, 6]]
[[1, 2], [3, 6], [4, 5]]
[[1, 3], [2, 4], [5, 6]]
[[1, 3], [2, 5], [4, 6]]
[[1, 3], [2, 6], [4, 5]]
[[1, 4], [2, 3], [5, 6]]
[[1, 4], [2, 5], [3, 6]]
[[1, 4], [2, 6], [3, 5]]
[[1, 5], [2, 3], [4, 6]]
[[1, 5], [2, 4], [3, 6]]
[[1, 5], [2, 6], [3, 4]]
[[1, 6], [2, 3], [4, 5]]
[[1, 6], [2, 4], [3, 5]]
[[1, 6], [2, 5], [3, 4]]
</code></pre>

<p>... and so on.</p>

<p>The CAS called Maple has this function implemented under the name <a href="http://www.maplesoft.com/support/help/Maple/view.aspx?path=combinat/setpartition" rel="nofollow">setpartition</a>.</p>

<p>Edit: fixed a critical late night typing error pointed out by wks, and clarified the outputs.</p>
