Monday, May 14, 2012

Partitioning a sequence into sets of unique pairs

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.



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



and split it into the following 3 combinations:



[[1, 2], [3, 4]]
[[1, 3], [2, 4]]
[[1, 4], [2, 3]]


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



[1,2,3,4,5,6]


splits into the following 15 combinations:



[[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]]


... and so on.



The CAS called Maple has this function implemented under the name setpartition.



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





No comments:

Post a Comment