mam rozwiązanie, ale nie skaluje się bardzo dobrze:
findBiggestSubmatrixNonContiguous <- function(A) {
A <- !is.na(A); ## don't care about non-NAs
howmany <- expand.grid(nr=seq_len(nrow(A)),nc=seq_len(ncol(A)));
howmany <- howmany[order(apply(howmany,1L,prod),decreasing=T),];
for (ri in seq_len(nrow(howmany))) {
nr <- howmany$nr[ri];
nc <- howmany$nc[ri];
rcom <- combn(nrow(A),nr);
ccom <- combn(ncol(A),nc);
comcom <- expand.grid(ri=seq_len(ncol(rcom)),ci=seq_len(ncol(ccom)));
for (comi in seq_len(nrow(comcom)))
if (all(A[rcom[,comcom$ri[comi]],ccom[,comcom$ci[comi]]]))
return(list(ri=rcom[,comcom$ri[comi]],ci=ccom[,comcom$ci[comi]]));
}; ## end for
NULL;
}; ## end findBiggestSubmatrixNonContiguous()
Jest on oparty na założeniu, że jeśli matryca ma wystarczająco małą gęstość NAS, a następnie wyszukując największe podrzędne najpierw, dość szybko znajdziesz rozwiązanie.
Algorytm działa poprzez obliczenie iloczynu kartezjańskiego wszystkich liczy wierszy i liczy kolumn, które mogą być indeksowane z oryginalnej matrycy do wytworzenia podmatrycę. Zbiór par zliczeń jest następnie sortowany malejąco według rozmiaru submatrix, który byłby wytwarzany przez każdą parę zliczeń; innymi słowy, uporządkowane według iloczynu dwóch liczb. Następnie wykonuje iteracje po tych parach. Dla każdej pary oblicza ona wszystkie kombinacje indeksów wierszy i indeksów kolumn, które mogą zostać pobrane dla tej pary zliczeń, i próbuje każdej kombinacji po kolei, dopóki nie znajdzie submatrix zawierającej zero NA. Po znalezieniu takiej podsieci zwraca ten zbiór indeksów wierszy i kolumn jako listę.
Wynik jest poprawny, ponieważ próbuje podmacieć rozmiarów w porządku malejącym, więc pierwszy, który znajdzie, musi być największą (lub powiązaną z największą) możliwą submatrix, która spełnia warunek.
## OP's example matrix
A <- data.frame(C1=c(NA,NA,NA,NA,2L,NA),C2=c(1L,1L,1L,0L,NA,NA),C3=c(1L,8L,NA,1L,1L,NA),C4=c(NA,1L,1L,6L,1L,3L),C5=c(NA,1L,5L,1L,1L,NA),row.names=c('R1','R2','R3','R4','R5','R6'));
A;
## C1 C2 C3 C4 C5
## R1 NA 1 1 NA NA
## R2 NA 1 8 1 1
## R3 NA 1 NA 1 5
## R4 NA 0 1 6 1
## R5 2 NA 1 1 1
## R6 NA NA NA 3 NA
system.time({ res <- findBiggestSubmatrixNonContiguous(A); });
## user system elapsed
## 0.094 0.000 0.100
res;
## $ri
## [1] 2 3 4
##
## $ci
## [1] 2 4 5
##
A[res$ri,res$ci];
## C2 C4 C5
## R2 1 1 1
## R3 1 1 5
## R4 0 6 1
Widzimy, że funkcja działa bardzo szybko, na przykład matrycy op, a zwraca poprawny wynik.
randTest <- function(NR,NC,probNA,seed=1L) {
set.seed(seed);
A <- replicate(NC,sample(c(NA,0:9),NR,prob=c(probNA,rep((1-probNA)/10,10L)),replace=T));
print(A);
print(system.time({ res <- findBiggestSubmatrixNonContiguous(A); }));
print(res);
print(A[res$ri,res$ci,drop=F]);
invisible(res);
}; ## end randTest()
pisałem wyżej funkcji, aby testowanie łatwiejsze. Możemy go nazwać, aby przetestować losową matrycę wejściową o rozmiarze NR przez NC, z prawdopodobieństwem wyboru NA w dowolnej komórce probNA.
Oto kilka trywialne testy:
randTest(8L,1L,1/3);
## [,1]
## [1,] NA
## [2,] 1
## [3,] 4
## [4,] 9
## [5,] NA
## [6,] 9
## [7,] 0
## [8,] 5
## user system elapsed
## 0.016 0.000 0.003
## $ri
## [1] 2 3 4 6 7 8
##
## $ci
## [1] 1
##
## [,1]
## [1,] 1
## [2,] 4
## [3,] 9
## [4,] 9
## [5,] 0
## [6,] 5
randTest(11L,3L,4/5);
## [,1] [,2] [,3]
## [1,] NA NA NA
## [2,] NA NA NA
## [3,] NA NA NA
## [4,] 2 NA NA
## [5,] NA NA NA
## [6,] 5 NA NA
## [7,] 8 0 4
## [8,] NA NA NA
## [9,] NA NA NA
## [10,] NA 7 NA
## [11,] NA NA NA
## user system elapsed
## 0.297 0.000 0.300
## $ri
## [1] 4 6 7
##
## $ci
## [1] 1
##
## [,1]
## [1,] 2
## [2,] 5
## [3,] 8
randTest(10L,10L,1/3);
## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
## [1,] NA NA 0 3 8 3 9 1 6 NA
## [2,] 1 NA NA 4 5 8 NA 8 2 NA
## [3,] 4 2 5 3 7 6 6 1 1 5
## [4,] 9 1 NA NA 4 NA NA 1 NA 9
## [5,] NA 7 NA 8 3 NA 5 3 7 7
## [6,] 9 3 1 2 7 NA NA 9 NA 7
## [7,] 0 2 NA 7 NA NA 3 8 2 6
## [8,] 5 0 1 NA 3 3 7 1 NA 6
## [9,] 5 1 9 2 2 5 NA 7 NA 8
## [10,] NA 7 1 6 2 6 9 0 NA 5
## user system elapsed
## 8.985 0.000 8.979
## $ri
## [1] 3 4 5 6 8 9 10
##
## $ci
## [1] 2 5 8 10
##
## [,1] [,2] [,3] [,4]
## [1,] 2 7 1 5
## [2,] 1 4 1 9
## [3,] 7 3 3 7
## [4,] 3 7 9 7
## [5,] 0 3 1 6
## [6,] 1 2 7 8
## [7,] 7 2 0 5
nie wiem łatwy sposób sprawdzenia, czy powyższy wynik jest prawidłowy, ale wygląda mi dobrze. Ale wygenerowanie tego wyniku zajęło prawie 9 sekund.Uruchomienie tej funkcji na umiarkowanie większych macierzach, szczególnie macierzy 77x132, jest prawdopodobnie przegraną przyczyną.
Oczekiwanie, aby zobaczyć czy ktoś może wymyślić genialny skuteczne rozwiązanie ...
nie jest 'A [C (2,4,5), 3: 5] 'najlepszym rozwiązaniem z 9 komórek? – bgoldst
Z matrycą 77x132 rozważasz około 2^(77 + 132) ~ 8.2E62 możliwych podmatryc. Ciekawi mnie, jak można to rozwiązać ... – Frank
@bgoldst lub o to chodzi 'A [2: 4, c (2, 4, 5)]' – MichaelChirico