Chaining list of vectors

Question

If I have a list of vectors such as below

list.x <- list(1:2, 1:3, 3:4, 5, 5:6)

Is there a way to replace each list element with an element that includes all the other values that the element can be paired with?

For example the first element (list.x[[1]]) would be replace with 1:4 because element 2 (list.x[[2]]) shows that 2, is also paired with 3, and element 3 shows that 3 is also paired with 4.

The final result I would like to achieve would be this list

final.list <- list(1:4, 1:4, 1:4, 5:6, 5:6)

Seems like a graph theory problem. `igraph` probably has something. Your list defines edges and you want to find the nodes in each connected component. — Gregor Thomas, Jun 27 '17 at 20:31
Actually, I'd even suggest [this as a dupe](https://stackoverflow.com/q/30407769/903061). You just need to make the graph object, run `igraph::components` on it, and format the results how you want. — Gregor Thomas, Jun 27 '17 at 20:35
Thanks, I will need to learn about the graph objects. Do you know if this will work if my list of vectors is a list of character vectors? — ColinTea, Jun 27 '17 at 20:46
I know that converting between a list of numeric and a list of characters is pretty trivial, so it shouldn't matter. If it does, just convert. — Gregor Thomas, Jun 27 '17 at 20:49

pwilcox · Answer 1 · 2017-06-28T13:49:56.790

I needed a change of pace today, so I decided to try to answer the question using base R. Here it goes:

First, I created a function that unions two vectors if they intersect, and if not, simply returns the first vector:

expand.if.toucing <- function(vector1, vector2) {

  i = intersect(vector1, vector2);

  if (NROW(i) > 0) 
    union(vector1, vector2) 
  else 
    vector1;

}

Then I made a function that merges one element in the list of vectors with another:

list.reduce <- function (lst) {

  for(v1 in 1:NROW(lst)) 
    for (v2 in 1:NROW(lst)) {

      if (v1 == v2) 
        next; 

      prevLength <- NROW(lst[[v1]]);

      lst[[v1]] <- expand.if.toucing(lst[[v1]], lst[[v2]]);

      newLength <- NROW(lst[[v1]]);

      if (newLength == prevLength)
        next;

      return(lst[-v2]);

    }

  lst;

}

After this, I made a function that merges all vectors in the list that can be merged. This is sort of a proto cluster analysis, so I called it clusterize:

clusterize <- function (lst) {

  reduced = TRUE;

  while(reduced) {

    prevLength <- NROW(lst);

    lst <- list.reduce(lst);

    newLength <- NROW(lst);

    reduced <- prevLength != newLength;

  }

  lst;
}

Now it's just a matter of replacing each element in the original list with its associated cluster:

replace.with.clusters <- function(lst, clusters) {

  for(l in 1:NROW(lst))
    for(c in 1:NROW(clusters)) {
      lst[[l]] <- expand.if.toucing(lst[[l]], clusters[[c]]);
      next;
    }

  lst;

}

You're good to go. The two main functions are clusterize and replace.with.cluster. Use them like this:

list.x <- list(1:2, 1:3, 3:4, 5, 5:6)
clusters <- clusterize(list.x);
replace.with.clusters(list.x, clusters);

# Outputs the following:
#
# [[1]]
# [1] 1 2 3 4
# 
# [[2]]
# [1] 1 2 3 4
# 
# [[3]]
# [1] 3 4 1 2
# 
# [[4]]
# [1] 5 6
# 
# [[5]]
# [1] 5 6

The third element is in a different order than your list, but from the way you describe the problem, order is not truly relevant.

Chaining list of vectors

1 Answers1