Отфильтруйте пары элементов так, чтобы каждый элемент находился только в одной паре - PullRequest
Новая
       9

Отфильтруйте пары элементов так, чтобы каждый элемент находился только в одной паре

1 голос
/ 06 февраля 2020

У меня есть фрейм данных, содержащий пары взаимодействующих элементов. Я хочу отфильтровать пары так, чтобы каждый элемент встречался только в одной паре. Какая пара хранится для каждого элемента, должна быть выбрана случайным образом. 

df <- data.frame(element1=c("A","A","B","B","B","C","C","D"), 
                 element2=c("B","C","D","E","C","D","E","F"),
                 stringsAsFactors = FALSE)

Пример ввода: 

Element1   Element2   
A          B        
A          C   
B          D       
B          E
B          C
C          D
C          E 
D          F

Желаемый вывод, например: 

Element1   Element2   
A          B
C          E
D          F

Спасибо за вашу помощь.

Ответы [ 3 ]

3 голосов
/ 07 февраля 2020

Простой igraph метод, который не очень удобен для хранения большинства данных. Но это гарантирует максимум одно соединение на элемент. 

library(igraph)
gr <- graph_from_data_frame(df, directed = FALSE)

for (vertex in sample(V(gr))) {
  if (degree(gr)[vertex] > 1) {
    edges <- E(gr)[.inc(vertex)]
    to_remove <- sample(edges, length(edges) - 1)
    gr <- delete_edges(gr, to_remove)
  }
}
as_data_frame(gr)

Возможно, вы можете сделать немного лучше, предварительно упорядочив вершины.

1 голос
/ 06 февраля 2020

Я не уверен, что это точно отвечает на ваш вопрос, но вот способ выбрать первое вхождение каждого элемента. Он сохраняет уникальность, которую вы упомянули, но не выбран случайным образом. 

    new_e1 <- c()
    new_e2 <- c()

    for(i in 1:nrow(df)) {
        e1 <- df[i, "element1"]
        e2 <- df[i, "element2"]
        if (!(e1 %in% new_e1) && !(e2 %in% new_e2) &&
            !(e1 %in% new_e2) && !(e2 %in% new_e1)) {
                new_e1 <- c(new_e1, e1)
                new_e2 <- c(new_e2, e2)
        }
    }

    new_df <- data.frame(element1 = new_e1, element2 = new_e2, stringsAsFactors = FALSE)

Я уверен, что есть более разумные способы написания этого кода, но я надеюсь, что это поможет.

0 голосов
/ 07 февраля 2020

В этом игрушечном примере вы можете подойти к нему как к задаче оптимизации с бинарными переменными, представляющими, какие строки выбраны, и с такими ограничениями, что каждая переменная выбирается один раз. 

el <- sort(unique(c(df$element1, df$element2)))
A <- matrix(0L, nrow=length(el), ncol=nrow(df), dimnames=list(el, sample(nrow(df))))
i <- match(unlist(df), rownames(A))
j <- match(rep(1L:nrow(df), ncol(df)), colnames(A))
A[cbind(i, j)] <- 1L

ans <- lp(direction="min",
    objective.in=rep(1L, nrow(df)),
    const.mat=A,
    const.dir="==",
    const.rhs=rep(1L, length(el)),
    all.bin=TRUE)
df[colnames(A)[as.logical(ans$solution)], ]

output: 

  element1 element2
2        A        C
4        B        E
8        D        F
...