帶有偶數個元素的集合的分區

Question

是否有任何有效的方法將集合{1, ... , 2*n}的所有分區列入n對中？

最簡單的想法是列出所有排列，然後排列(a1, a2, ... , a8)意味着劃分{{a1,a2}, ... , {a7,a8}}。在這種情況下，每個部門有2^n * n!排列。這是O((2n)!)。

我可以找到更有效的方法嗎？

Answer 1

這是我的筆和紙的算法：

f(set,result): 
    if the set is empty: 
    return result 
    otherwise: 
    pair one item from the set with 
    each of the remaining items, 
    calling f again with the pair added to 
    the result and out of the set 

123456 
12 34 56 
    35 46 
    36 45 
13 24 56 
    25 46 
    26 45 
14 23 56 
    25 36 
    26 35 
...