If rows has a similar element, keep the shorter row

I had to use a while loop, maybe there's a less loopy solution...

foo <- function(x) {
  i <- 1
  while(i < nrow(x)) {
    grps <- strsplit(x$groups, " ")
    keep <- unlist(lapply(grps, function(x) identical(x, grps[[i]]) | !any((length(x) > length(grps[[i]]) & duplicated(c(grps[[i]], x))))))
    x <- x[keep,]
    i <- i+1
  }
  x
}

foo(x)
  cluster                              groups chr
1       1                   20000127 20000128  17
3       3 20000129 20000130 20000131 20000132  35
4       4 20000133 20000134 20000135 20000136  35

Explanation.

# I created a function to keep things compact and allow it to be used for other datasets. 
# The `x` is the argument, assumed to be your data frame.
# 1: foo <- function(x) {

# Start the ball rolling with a counter to use in the while loop.
# 2: i <- 1

# This starts the while loop and will continue until "i" reaches the end of the data. 
# But note later that the data may change if there are rows that meet your condition.
# 3: while(i < nrow(x)) {

# Split the groups variable at the " " and store in "grps"
# 4: grps <- strsplit(x$groups, " ")

# This next line does the work. 
# It creates a vector of logical indices which are used to remove rows of "x"
# I split this into many lines to explain better.

# 5: keep <- unlist(lapply(grps, function(x) # apply a function to "grps"
#     identical(x, grps[[i]]) |  # Returns TRUE for each row we are checking
#     !any(  # Negate the next conditions. They will return rows to remove.
#         (length(x) > length(grps[[i]]) & # return TRUE (negated=FALSE) if the length of each x is more than all others
#         duplicated(c(grps[[i]], x))))))  # if duplicated, return TRUE (negated=FALSE)

# Update "x" by keeping only the rows that meet the criteria defined in step 5.
# 6:    x <- x[keep,]

# Increase i
# 7:    i <- i+1
# 8:  } # This ends the while loop
# 9:  x # Return the result
} # End of function

Exploring this problem has been fun. I've learned that this is a variation of the set cover problem and is NP Complete.

It would help to understand the scope of your problem. If we are talking 10s of clusters, we could use brute force. If it's thousands of clusters, we are going to have to use an approximation.

I have learned there is an R implementation of the greedy algorithm in the RcppGreedySetCover package.

First we need to convert to two column long form. We can use dplyr.

library(tidyverse)
longx <- x %>% 
    mutate(splitgroups = strsplit(as.character(groups), " ")) %>%
    unnest(splitgroups) %>% select(cluster, splitgroups)

Then we can use greedySetCover to approximate the smallest set that covers all elements.

library(RcppGreedySetCover)
greedySetCover(longx)
#100% covered by 3 sets.
#    cluster splitgroups
# 1:       2    20000127
# 2:       3    20000129
# 3:       3    20000130
# 4:       3    20000131
# 5:       3    20000132
# 6:       5    20000128
# 7:       5    20000133
# 8:       5    20000134
# 9:       5    20000135
#10:       5    20000136

This suggests the set of 2,3, and 5 covers everything. But this does not fully answer your question, because, as you know there is a set of clusters that is shorter.

However, what we have learned, is that the minimum set is 3 clusters. Now we can test all combinations of 3 clusters.

set.size <- length(unique(greedySetCover(longx)$cluster))
binary.matrix <- table(longx)
combinations <- combn(unique(x$cluster),set.size)

total.lengths <- apply(combinations,2,function(x){
  if(sum(as.logical(colSums(binary.matrix[x,]))) == ncol(binary.matrix))
    {sum(rowSums(binary.matrix[x,]))} 
  else {NA}})

min.length <- min(total.lengths,na.rm = TRUE)
min.set <- combinations[,which(total.lengths == min.length)]
x[min.set,]
#  cluster                              groups chr
#1       1                   20000127 20000128  17
#3       3 20000129 20000130 20000131 20000132  35
#4       4 20000133 20000134 20000135 20000136  35

Data

x <- data.frame(cluster=c(1,2,3,4,5),
                groups=c('20000127 20000128',
                         '20000127 20000128 20000134',
                         '20000129 20000130 20000131 20000132',
                         '20000133 20000134 20000135 20000136',
                         '20000128 20000133 20000134 20000135 20000136'),
                chr=c(17,26,35,35,44), stringsAsFactors=FALSE)