Самый большой набор столбцов, имеющий не менее k общих строк

У меня есть большой фрейм данных (50k на 5k). Я хотел бы сделать меньший фрейм данных, используя следующее правило. Для заданного k, 0>k>n, я хотел бы выбрать наибольший набор столбцов, чтобы k строк имели значения, отличные от na, во всех этих столбцах.

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

Кажется, мой способ сделать это слишком сложен. Он основан на (1) вычислении списка всех возможных подмножеств набора столбцов, а затем (2) проверке количества общих строк, которые у них есть. Для даже небольшого количества столбцов (1) становится слишком медленным (например, 45 секунд для 25 столбцов).

Вопрос. Возможно ли теоретически получить наибольший набор столбцов, разделяющих не менее k строк, отличных от na? Если да, то какой более реалистичный подход?

элегантный ответ @alexis_laz на аналогичный вопрос использует обратный подход к моему, исследуя все (фиксированного размера) подмножества < em>наблюдения/выборки/отрисовки/единицы и проверка того, какие переменные присутствуют в них.

При большом n сложно комбинировать n наблюдений. Например, length(combn(1:500, 3, simplify = FALSE)) дает 20 708 500 комбинаций для 500 наблюдений и не может создать комбинации на моем компьютере для размеров больше 3. Это заставляет меня беспокоиться, что это невозможно для больших n и p ни при одном подходе.

Я включил пример матрицы для воспроизводимости.

require(dplyr)

# generate example matrix
set.seed(123)
n = 100
p = 25
missing = 25
mat = rnorm(n * p)
mat[sample(1:(n*p), missing)] = NA
mat = matrix(mat, nrow = n, ncol = p)
colnames(mat) = 1:p

# matrix reporting whether a value is na
hasVal = 1-is.na(mat)

system.time(
  # collect all possible subsets of the columns' indices
  nameSubsets <<- unlist(lapply(1:ncol(mat), combn, x = colnames(mat), simplify = FALSE), 
                         recursive = FALSE, 
                         use.names = FALSE)
)

#how many observations have all of the subset variables
countObsWithVars = function(varsVec){
  selectedCols = as.matrix(hasVal[,varsVec])
  countInRow = apply(selectedCols, 1, sum) # for each row, number of matching values
  numMatching = sum(countInRow == length(varsVec)) #has all selected columns
}
system.time(
  numObsWithVars <<- unlist(lapply(nameSubsets, countObsWithVars))
)

# collect results into a data.frame
df = data.frame(subSetNum = 1:length(numObsWithVars), 
                numObsWithVars = numObsWithVars,
                numVarsInSubset = unlist(lapply(nameSubsets, length)),
                varsInSubset = I(nameSubsets)) 

# find the largest set of columns for each number of rows
maxdf = df %>% group_by(numObsWithVars) %>%
  filter(numVarsInSubset== max(numVarsInSubset)) %>%
  arrange(numObsWithVars)