首页 文章

在 R 中将向量详尽划分为成对的方法

提问于
浏览 次
5

(这是受到另一个标记为重复的问题的启发。尽管我可能是 ignorant.)，但我还是认为这是一个有趣的问题，尽管组合方法可能有一个简单的解决方案。

问题

对于长度为n的向量，其中n mod 2为零，请找到所有可能的方法将向量的所有元素划分为对，而无需替换，顺序无关紧要。

例如，对于向量c(1,2,3,4)：

list(c(1,2), c(3,4))
list(c(1,3), c(2,4))
list(c(1,4), c(2,3))

我的方法如下(对于新手代码，请提前道歉)：

# write a function that recursively breaks down a list of unique pairs (generated with combn). The natural ordering produced by combn means that for the first pass through, we take as the starting pair, all pairings with element 1 of the vector with all other elements. After that has been allocated, we iterate through the first p/2 pairs (this avoids duplicating).

pairer2 <- function(kn, pair_list) {

  pair1_partners <- lapply(kn, function(x) {

    # remove any pairs in the 'master list' that contain elements of the starting pair.
    partners <- Filter(function(t) !any(t %in% x), pair_list)

    if(length(partners) > 1) {

    # run the function again
      pairer2(kn = partners[1:(length(partners)/2)], partners)
    } else {return(partners)}
  })

    # accumulate results into a nested list structure
  return(mapply(function(x,y) {list(root = x, partners = y)}, kn, pair1_partners, SIMPLIFY = F))
}

# this function generates all possible unique pairs for a vector of length k as the starting point, then runs the pairing off function above

pair_combn <- function(k, n = 2) {

  p <- combn(k, n, simplify = F)

  pairer2(kn = p[1:(length(k)-1)], p)}

# so far a vector k = 4
pair_combn(1:4)

[[1]]
[[1]]$root
[1] 1 2

[[1]]$partners
[[1]]$partners[[1]]
[1] 3 4

[[2]]
[[2]]$root
[1] 1 3

[[2]]$partners
[[2]]$partners[[1]]
[1] 2 4

[[3]]
[[3]]$root
[1] 1 4

[[3]]$partners
[[3]]$partners[[1]]
[1] 2 3

据我所知，它也适用于较大的k。这不是那么有效，可能是因为Filter对于大列表来说很慢，并且我不得不承认我无法将嵌套列表(这是可能的解决方案的树形表示)折叠到每个分区的列表中。感觉应该有一个更优雅的解决方案(在 R 中)？

提醒您，有趣的是，此递归方法生成了可能解决方案的简约表示(尽管不方便)。

r recursion functional-programming combinatorics

2 回答

  • 1

    这是一种方法：

    > x <- c(1,2,3,4)
> xc <- combn(as.data.frame(combn(x, 2)), 2, simplify = FALSE)
> Filter(function(x) all(1:4 %in% unlist(x)), xc)
[[1]]
  V1 V6
1  1  3
2  2  4

[[2]]
  V2 V5
1  1  2
2  3  4

[[3]]
  V3 V4
1  1  2
2  4  3

> ```
 
More generally:
 
```java
pair_combn <- function(x) {
    Filter(function(e) all(unique(x) %in% unlist(e)),
           combn(as.data.frame(combn(x, 2)),
                 length(x)/2, simplify = FALSE))
}
    回复于
  • 1

    感谢您继续我的问题(由于某些奇怪的原因被标记为重复)。我认为对于 k> = 10 来说，没有解决方案会很好。对于 k=6，盖茨基的答案对我不起作用(实际上有 15 种可能性时，它会返回 5 种可能性)。 Ista 的解在 k = 12 时失败。

    回复于

相关问题