Znajdź wszystkie kombinacje liczb, które sumują się do celu.

Question

Chciałbym znaleźć najszybszy sposób, aby znaleźć do 1000 możliwych kombinacji liczb całkowitych "n", aby znaleźć docelową liczbę całkowitą.

Na przykład. Powiedzmy, że chciałem zsumować liczbę "20". Chcę znaleźć do 1000 kombinacji czterech liczb całkowitych, które sumują się do tej liczby. Liczby całkowite mogą się powtarzać. Mam też warunek, że liczba całkowita nie może być mniejszy niż określony numer, w tym przypadku 4.

target<-20 #the number I wish to sum to 
lowest<-4 #the smallest integer I allow 
size<-4 #the number of integers I wish to use to sum 
maxposs <- target - ((size-1) * lowest) #given the lowest, this is the max possible integer. In my example it is 8. 

ten sposób zacząłem pracować na to uwagę. Użyj combn, aby znaleźć wszystkie kombinacje czterech wybranych liczb całkowitych, a następnie filtrowanie przez te, które sumują się do mojego celu.

m <- combn(rep(lowest:maxposs,size), size) 
m1<- m[,colSums(m)==target] 

Tutaj 'm1' ma 245 kolumn. Jest tylko tyle rozwiązań. W ciągu ostatnich kilku kolumn:

#  [,238] [,239] [,240] [,241] [,242] [,243] [,244] [,245] 
#[1,]  4  4  4  4  4  4  5  5 
#[2,]  5  5  5  6  7  4  6  4 
#[3,]  7  4  5  4  4  5  4  5 
#[4,]  4  7  6  6  5  7  5  6 

Jednak moim rzeczywistej aplikacji, mogę mieć do czynienia z bardzo wysokie liczby całkowite (podsumowując 1000) i chcą ograniczyć się do losowej próbie 1000 możliwych kombinacji. Ponieważ jest to test statystyczny z randomizacją, prędkość jest istotna. Zastanawiam się, czy ktoś wie o szybszym sposobie robienia tego. Moja droga nie jest intuicyjnie szybka.

Answer 1

my_matrix <- matrix(nrow = 1000, ncol = 4) 
i <- 1 
nn <- 1000 
while(i <= 1000){ 
    x <- sample(x = 4:nn, size = 3) 
    y = nn - sum(x) 
    if(y >= 4){ 
    my_matrix[i, ] <- c(x, y) 
    i <- i + 1 
    } 
} 

Sugestia Per Gavina, przerobiona z macierzą wcześniej przydzieloną. Teraz działa w .158 sekund, dwa razy szybciej i prawdopodobnie lepiej się skaluje.