如果两个向量具有相同的交点，则分配相同的索引 [英] Assign the same index if two vectors have a common intersection

问题描述

在与我的其他一些问题紧密相关的问题上，我需要帮助.

I need help with a question closely related to some other question of mine.

正如问题的标题所言，我想在向量中生成一个索引，以将列表中的不同向量相交，如果它们有交点，或者如果两者都不与列表中的其他向量相交，则将它们链接起来，等等.上...

As the title of the question says, I want to generate an index in a vector that links different vectors in a list if they have an intersection or, if not, if both intersect with some other vector in a list, and so on...

这是一个涉及图论/网络的问题-我想找到间接连接的向量.

This is a question involving graph theory/networks - I want to find indirectly connected vectors.

以上问题解决了我在一个数据帧中考虑两列的问题，但是我不知道如何将其概括为一个元素长度不同的列表.

The question above solved my problem considering two columns a dataframe, but I don't know how to generalize this to a list in which elements my have different lengths.

这是一个示例:list(1:3, 3:5, 5, 6)应该给我c(1, 1, 1, 2)

This is an example: list(1:3, 3:5, 5, 6) should give me c(1, 1, 1, 2)

编辑:

我尝试使用邻接矩阵的幂表示从一条边到另一条边的可能路径这一事实.

I've tried using the fact that the powers of an adjacency matrix represent possible paths from one edge to some other one.

find_connections <- function(list_vectors){
  
  list_vectors <- list_vectors %>%
    set_names(paste0("x", 1:length(list_vectors)))
  
  x <- crossprod(table(stack(list_vectors)))
  
  power <- nrow(x) - 2
  
  x <- ifelse(x >= 1, 1, 0)
  
  
  if(power > 0){
    z <- accumulate(replicate(power, x, simplify = FALSE),
                    `%*%`, .init = x) %>% 
      reduce(`+`) 
  } else{
    z <- x
  }
  
  z <- ifelse(z >= 1, 1, 0)
  
  w <- z %>%
    as.data.frame() %>%
    group_by(across()) %>%
    group_indices()
  
  return(w)
}

问题是运行我的代码花了太长时间.每个矩阵不是很大，但是我确实需要在大量矩阵上运行该函数.

The problem is that it took too long to run my code. Each matrix is not very large, but I do need to run the function on a large number of them.

有可能对此进行改善吗?

Is it possible to improve this?

推荐答案

这是一种实现方法.它为每个向量中的元素创建一个循环，然后使用与上一个答案相同的技巧来查找聚类.

This is one way to do it. It creates a loop for the elements in each vector and then uses the same trick as the previous answer to find clusters.

library(data.table)
library(igraph)
x <- list(1:3, 3:5, 5, 6)
dt <- rbindlist(lapply(x, 
  function(r) data.table(from = r, to = shift(r, -1, fill = r[1]))))
dg <- graph_from_data_frame(dt, directed = FALSE)
unname(sapply(x, function(v) components(dg)$membership[as.character(v[1])]))
#> [1] 1 1 1 2

这篇关于如果两个向量具有相同的交点，则分配相同的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！