R 행 제한이있는 expand.grid

Question

길이가 N 인 숫자 벡터 x가 있고 다음 세트의 집합 내 합계 벡터를 만들려고합니다. 최대 x 자의 가능한 모든 조합 각 조합의 요소. 나는 천천히 반복적 인 접근법을 사용했다. 내가 여기서 찾고있는 것은 루프를 사용하지 않는 방법이다.

N이 ME (22 이상) 커질 같이 expand.grid 출력되고, 그러나 N = 5, M = 4

M <- 4 
x <- 11:15 
y <- as.matrix(expand.grid(rep(list(0:1), length(x)))) 
result <- y[rowSums(y) <= M, ] %*% x 

와 다음 예 I이 고려 된 접근법을 고려 너무 크고 오류가 발생합니다 (위의 x를 x < - 11:55로 바꾸십시오). 이상적으로 전체 행렬을 구성하기 전에 행에 대한 제한을 허용하는 expand.grid 함수가있을 것입니다.이 행렬은 행렬 크기를 메모리 제한 내에서 유지할 수 있습니다.

큰 N에 문제를 일으키지 않고이를 달성 할 수있는 방법이 있습니까?

Answer 1

이 시도 :

는

c(0, unlist(lapply(1:M, function(k) colSums(combn(x, k))))) 

은 테스트 데이터를 다음과 같이 당신의 expand.grid 접근 방식과 동일한 결과를 생성합니다.

M <- 4 
x <- 11:15 

# expand.grid approach 
y <- as.matrix(expand.grid(rep(list(0:1), length(x)))) 
result <- y[rowSums(y) <= M, ] %*% x 

# combn approach 
result1 <- c(0, unlist(lapply(1:M, function(k) colSums(combn(x, k))))) 

all(sort(result[,1]) == sort(result1)) 
# [1] TRUE 

이 빠르게해야한다 (이것은 내 컴퓨터에 0.227577 초 소요 N = 22, M = 4) : 당신이

로 합의 고유 한 값을 선택 할 수 있습니다

x <- 1:22 # N = 22 
M <- 4 
c(0, unlist(lapply(1:M, function(k) colSums(combn(x, k))))) 
# [1] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 3 4 5 6 7 

unique(c(0, unlist(lapply(1:M, function(k) colSums(combn(x, k)))))) 

Answer 2

귀하의 문제는 엄청난 양의 조합과 관련이 있습니다. 당신이하고있는 것처럼 보이는 것은 길이가 x 인 순서로 0과 1의 모든 다른 조합을 나열하는 것입니다.

예제에서 x는 길이가 5이고 2^5 = 32 조합입니다. x 길이가 22 일 때 2^22 = 4194304 조합이 있습니다.

대신 이진 인코딩을 사용할 수 없습니까? 그것은 완전히 문제가 해결되지 않습니다,하지만 당신은 얻을 수 있어야

00011 에 대한 00010 3 스탠드에 대한 00001 2 스탠드에 대한 00000 1 스탠드에 대한 0 스탠드를 의미 할 것입니다 귀하의 경우에는 ... 지금보다 조금 더.