R - все совпадающие пары элементов вектора

Question

Я ищу, чтобы идентифицировать все возможные попарные соответствия элементов вектора. Я не буду теперь число элементов вектора, поэтому length (vector) = n, но я буду знать только, что n четно. Порядок не имеет значения, но каждый раз пары должны складываться до исходного вектора.

К примеру, если x<-c(1,2,3,4) ответ 3, а именно:

1) (1,2)(3,4) 
2) (1,3)(2,4) 
3) (1,4)(2,3) 

Есть немало подобных нитей, но я пропускаю ту часть, где пары группируются, чтобы сформировать начальный вектор.

Спасибо!

Answer 1

Каждое упорядоченное спаривание n элементов (где n равномерно) эквивалентно случайной перестановке (1:n) %% (n/2). Кроме того, поскольку порядок пар не имеет значения, перестановки, равные значению, фактически эквивалентны. Например, c(1,1,0,0) эквивалентно c(0,0,1,1) - оба из них соединяют первые два элемента вместе и последние два элемента вместе. Таким образом, мы можем получить уникальный набор дополнив каждую перестановку, а затем повторно маркируя элементы каждой перестановки в том порядке, что они появляются, а затем принимать только уникальные одни из результата:

library(magrittr) 
library(combinat) 

all_pairings <- function(n) { 
    if (n %% 2 != 0) 
     stop("n must be even") 
    allperms <- permn((1:n) %% (n/2)) 
    allperms %<>% lapply(. %>% factor(levels=unique(.)) %>% as.numeric) 
    unique(allperms) 
} 

Это дает нам правильный результат при п = 4:

> all_pairings(4) 
[[1]] 
[1] 1 2 1 2 

[[2]] 
[1] 1 2 2 1 

[[3]] 
[1] 1 1 2 2 

Чтобы действительно получить пар, использовать split функцию:

> lapply(all_pairings(4), split, x=letters[1:n]) 
[[1]] 
[[1]]$`1` 
[1] "a" "c" 

[[1]]$`2` 
[1] "b" "d" 


[[2]] 
[[2]]$`1` 
[1] "a" "d" 

[[2]]$`2` 
[1] "b" "c" 


[[3]] 
[[3]]$`1` 
[1] "a" "b" 

[[3]]$`2` 
[1] "c" "d" 

Если вам нужно только количество уникальных спариваний и не полный список из них, есть явная формула: http://www.regentsprep.org/regents/math/algebra/apr2/LpermRep.htm

В этом случае формула для уникальных парных элементов из N элементов будет равна factorial(n)/2^(n/2)/factorial(n/2). Первый член представляет собой все перестановки, второй термин представляет избыточность из-за эквивалентных переупорядочений внутри пары, а третий член представляет избыточность из-за переупорядочения пар.

num_pairings <- function(n) { 
    if (any(n %% 2 != 0)) 
     stop("n must be even") 
    factorial(n)/(2^(n/2))/factorial(n/2) 
} 


> n <- seq(2,20, by=2); data.frame(n=n, NumPairings=num_pairings(n)) 
data.frame with 10 rows and 2 columns 
      n NumPairings 
    <numeric> <numeric> 
1   2   1 
2   4   3 
3   6   15 
4   8   105 
5   10   945 
6   12  10395 
7   14  135135 
8   16  2027025 
9   18 34459425 
10  20 654729075