<p>如果要将1:n的所有分区枚举为对,可以递归地进行。
这是一个R解。在</p>
<pre><code>f <- function(x) {
# We can only partition the set into pairs
# if it has an even number of elements
stopifnot( length(x) %% 2 == 0 )
stopifnot( length(x) > 0 )
# To avoid double counting, sort the array,
# and put the first element in the first pair
x <- sort(x)
# The first pair contains the first element
# and another element: n - 1 possibilities
first_pairs <- lapply( x[-1], function(u) c(x[1],u) )
if( length(x) == 2 ) { return( list( first_pairs ) ) }
# Progressively build the result, by considering
# those pairs one at a time
result <- list()
for( first_pair in first_pairs ) {
y <- setdiff( x, first_pair )
rest <- f(y)
# Call the function recursively:
# a partition of 1:n that starts with (1,2)
# is just (1,2) followed by a partition of 3:n.
result <- append(
result,
# This is the tricky bit:
# correctly use append/c/list to build the list.
lapply( rest, function (u) { append( list( first_pair ), u ) } )
)
}
result
}
# The result is a list of lists of 2-element vectors: print it in a more readable way.
result <- f(1:6)
result <- lapply( result, function (u) unlist(lapply( u, function (v) paste( "(", paste(v,collapse=","), ")", sep="" ))))
result <- unlist( lapply( result, function (u) paste( u, collapse=", " ) ) )
</code></pre>