Q:

Fastest way to extract k distinct elements from n pairs in R

Suppose I have n distinct unordered pairs of elements. I want to extract the smallest number of pairs that contain k distinct elements from the n pairs.
I am aware that I can use duplicated() to extract all the distinct elements from the n pairs, but I don't know how to use it to obtain the smallest number of pairs that contains k elements. 
Here is an example.
Suppose I have 8 pairs in a data.frame:
x_coord <- c("x1","x1","x1","x2","x2","x3","x4","x4")
y_coord <- c("y1","y2","y3","y1","y4","y5","y2","y5")
df <- data.frame(x_coord, y_coord)
df
  x_coord y_coord
1      x1      y1
2      x1      y2
3      x1      y3
4      x2      y1
5      x2      y4
6      x3      y5
7      x4      y2
8      x4      y5

If I use duplicated(), I obtain:
x_coord_vector = as.vector(df$x_coord)
y_coord_vector = as.vector(df$y_coord)
df_vector <- c(x_coord_vector, y_coord_vector)
distinct_elements <- df_vector[!duplicated(df_vector)]
distinct_elements
# [1] "x1" "x2" "x3" "x4" "y1" "y2" "y3" "y4" "y5"

If I want the smallest number of pairs that contain 6 distinct elements, the output should be:
df_6_distinct_elements
   x_coord y_coord
 1      x1      y1
 2      x1      y2
 3      x1      y3
 4      x2      y1
 5      x2      y4

Note that the function duplicated() might not even be efficient for such a task. Hence any suggestion is welcome.  

A:

I think this solves your problem. This finds the minimum rows to have at least n unique values in the pairs. It is possible that you will get n + 1 unique elements. 
x_coord <- c("x1","x1","x1","x2","x2","x3","x4","x4")
y_coord <- c("y1","y2","y3","y1","y4","y5","y2","y5")
df <- data.frame(x_coord, y_coord)

## Define the number of unique elements
n <- 6

## Get the ordered values and find the nth unique value 
uvals <- c(t(df))
fval <- uvals[which(!duplicated(uvals))[n]]

## Select the first column with the nth unique value
df[1:which(fval == df$x_coord | fval == df$y_coord)[1], ]
#   x_coord y_coord
# 1      x1      y1
# 2      x1      y2
# 3      x1      y3
# 4      x2      y1
# 5      x2      y4

