Как создать идентификаторы группы для эквивалентных предметов / частей?

Question

Набор данных представляет собой набор данных из 2 столбцов. Столбец 1 является оригинальным элементом. Столбец 2 представляет собой эквивалентную подпрограмму для исходного элемента. Цель состоит в том, чтобы создать идентификаторы группы, которые объединяют все эквивалентные части в один и тот же идентификатор группы.

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

#Sample data
set.seed(78)
x = data.frame(Original = sample(letters, 10), Sub = sample(letters, 10))


#Sample output is 'Group_ID' column
y = data.frame(Original = x$Original, Sub = x$Sub, Group_ID = c("Group_01", "Group_02", "Group_02", "Group_03", "Group_04", "Group_02", "Group_05", "Group_04", "Group_06", "Group_05"))

Ввод объекта x. Строка 1 указывает, что 't' и 'w' являются эквивалентными элементами и принадлежат группе. ROw 2 указывает, что 'u' и 'o' являются эквивалентными элементами и принадлежат группе и т. Д. ...

Вывод в столбце «Group_ID» в y.

Row1: t и w включены в Group_01 (первая строка, новая группа) Row2: u и o не встречаются ни в одной из предыдущих групп. Новая группа_02 создана Строка 3: «o» уже является частью Group_02 из строки 2. Таким образом, «u», «o», «i» являются эквивалентными и замещаемыми друг для друга. Итак, Group_02 используется здесь и так далее ...

С этими примерами данных можно видеть, что строки Group_02 повторяются 3 раза (строки 2,3,6) и Group_05 повторяются 2 раза (строки 7,10 с общей буквой f). элемент).

Answer 1

I второе @ предложение Грегора идентифицировать связанные компоненты графа, индуцированные x;Вот пример, основанный на ваших данных

library(igraph)
library(dplyr)
x %>%
    left_join(graph_from_data_frame(x) %>%
        components() %>%
        magrittr::extract2(1) %>%
        stack(),
        by = c("Original" = "ind")) %>%
    mutate(values = paste("Group", values, sep = ""))
#   Original Sub values
#1         t   w Group1
#2         u   o Group2
#3         o   i Group2
#4         r   p Group3
#5         s   g Group4
#6         i   z Group2
#7         f   e Group5
#8         g   l Group4
#9         b   a Group6
#10        v   f Group5

Объяснение: Составьте igraph из x, определите все подключенные компоненты и объедините идентифицированные метки группы с вашими исходными данными.

Пожалуйста, обратите внимание, что, похоже, ошибка в ожидаемом результате;строки 5 + 8 должны иметь одинаковую метку группы.