제약 행렬

Question

나는 모든 요소가 0에서 100까지의 정수는 크기 5 (5 × 5)의 모든 가능한 매트릭스를 만들 필요가

과의 합은 내가 그것을 할 방법을 잘 모르겠어요, 또는 100

입니다 시작하는 법 ... 어떤 제안?

나는 R 프로그램을 사용했지만, 어떻게해야하는지에 대한 아이디어를 찾고 있습니다. Pseucode는 좋습니다.

필자의 전나무 접근법은 100 개 요소의 모든 순열을 25 번 (행렬의 각 요소에 대해 하나씩) 얻은 다음 100을 합한 것만 가져옵니다.하지만 그것은 100^25 순열입니다. 이 방법으로.

감사 드리며 도움이 될 것입니다.

Answer 1

OP는 최대 길이가 100 인 모든 정수 파티션을 찾고 있습니다. partitions 패키지에는이 목적으로 정확히 restrictedparts이라는 기능이 있습니다. 예컨대 : 일단 모든 이들의 생성 된

library(partitions) 
## all integer partitions of 10 of maximal length = 4 
restrictedparts(10, 4)            
[1,] 10 9 8 7 6 5 8 7 6 5 6 5 4 4 7 6 5 4 5 4 3 4 3 
[2,] 0 1 2 3 4 5 1 2 3 4 2 3 4 3 1 2 3 4 2 3 3 2 3 
[3,] 0 0 0 0 0 0 1 1 1 1 2 2 2 3 1 1 1 1 2 2 3 2 2 
[4,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 2 2 

, 단순히 각 조합의 5 × 5 행렬을 (restrictedparts이 0 0 3 및 0 3 0 구분하지 않음) 만듭니다. 유일한 문제는 가능한 조합 (partitions::R(25, 100, TRUE) = 139620591)이 많아 restrictedparts(100, 25)에 전화 할 때 오류가 발생한다는 것입니다. restrictedparts에

가

test <- restrictedparts(100, 25) 

에러 (100, 25)의 NA는 외부 기능 호출 (ARG 3) 또한 : 경고 메시지가 restrictedparts에서 (100, 25)의 NA의 범위를 정수하기위한 강제 도입

우리가 restrictedparts를 통해 그들 모두를 생성 할 수 있기 때문에, 우리는 개별적과 함께 firstrestrictedpart를 사용하여 생성 할 수 있습니다 nextrestrictedpart과 같이 :

funPartition <- function(n) { 
    p <- firstrestrictedpart(100, 25) 
    mat <- matrix(nrow = 25, ncol = n) 
    mat[,1] <- p 
    for (i in 2:n) { 
     p <- nextrestrictedpart(p) 
     mat[,i] <- p 
    } 
    mat 
} 

head(funPartition(5)) 
    [,1] [,2] [,3] [,4] [,5] 
[1,] 100 99 98 97 96 
[2,] 0 1 2 3 4 
[3,] 0 0 0 0 0 
[4,] 0 0 0 0 0 
[5,] 0 0 0 0 0 
[6,] 0 0 0 0 0 

유일한 문제는 효율적이지 않다는 것입니다.

는 RcppAlgos가
(나는의 저자) 패키지 RcppAlgos를 사용하여 빠른 방법이 입력합니다.

library(RcppAlgos) 
combs <- comboGeneral(0:100,25,TRUE,"sum","==",100,rowCap=10^5) 
matrixCombs <- lapply(1:nrow(combs), function(x) matrix(combs[x,], nrow = 5, ncol = 5)) 

matrixCombs[1:3] 
[[1]] 
    [,1] [,2] [,3] [,4] [,5] 
[1,] 0 0 0 0 0 
[2,] 0 0 0 0 0 
[3,] 0 0 0 0 0 
[4,] 0 0 0 0 0 
[5,] 0 0 0 0 100 

[[2]] 
    [,1] [,2] [,3] [,4] [,5] 
[1,] 0 0 0 0 0 
[2,] 0 0 0 0 0 
[3,] 0 0 0 0 0 
[4,] 0 0 0 0 1 
[5,] 0 0 0 0 99 

[[3]] 
    [,1] [,2] [,3] [,4] [,5] 
[1,] 0 0 0 0 0 
[2,] 0 0 0 0 0 
[3,] 0 0 0 0 0 
[4,] 0 0 0 0 2 
[5,] 0 0 0 0 98 

당신이 정말로 순열, 아무 문제를 원한다면

, 단지 permuteGeneral 전화 :

perms <- permuteGeneral(0:100,25,TRUE,"sum","==",100,rowCap=10^5) 
matrixPerms <- lapply(1:nrow(perms), function(x) matrix(perms[x,], nrow = 5, ncol = 5)) 

matrixPerms[1:3] 
[[1]] 
    [,1] [,2] [,3] [,4] [,5] 
[1,] 0 0 0 0 0 
[2,] 0 0 0 0 0 
[3,] 0 0 0 0 0 
[4,] 0 0 0 0 0 
[5,] 0 0 0 0 100 

[[2]] 
    [,1] [,2] [,3] [,4] [,5] 
[1,] 0 0 0 0 0 
[2,] 0 0 0 0 0 
[3,] 0 0 0 0 0 
[4,] 0 0 0 0 100 
[5,] 0 0 0 0 0 

[[3]] 
    [,1] [,2] [,3] [,4] [,5] 
[1,] 0 0 0 0 0 
[2,] 0 0 0 0 0 
[3,] 0 0 0 0 100 
[4,] 0 0 0 0 0 
[5,] 0 0 0 0 0 

그것은뿐만 아니라 매우 빠릅니다. norm100Master을 의 래퍼로 사용하고 lapply(rep(5, runs), norm100)과 함께 두십시오.

funRcppAlgos <- function(myCap) { 
    perms <- permuteGeneral(0:100,25,TRUE,"sum","==",100,rowCap=myCap) 
    lapply(1:myCap, function(x) matrix(perms[x,], nrow = 5, ncol = 5)) 
} 

runs <- 5000 
microbenchmark(norm100Master(runs), funRcppAlgos(runs)) 
Unit: milliseconds 
       expr  min  lq  mean median  uq  max neval 
norm100Master(runs) 50.930848 56.413103 65.00415 57.341665 64.242075 125.5940 100 
funRcppAlgos(runs) 8.711444 9.382808 13.05653 9.555321 9.912229 116.9166 100 

그리고 (행렬로 변환 없음) 이상 funPartition와 정수 파티션의 유일한 세대를 비교, 우리는이 :

microbenchmark(nextPs = funPartition(10^4), 
       algos = comboGeneral(0:100,25,TRUE,"sum","==",100,10^4)) 
Unit: milliseconds 
    expr  min  lq  mean median  uq  max neval 
nextPs 317.778757 334.35560 351.68058 343.81085 355.03575 521.13181 100 
algos 9.438661 10.12685 10.60887 10.37617 10.85003 13.99447 100 

와 평등 테스트하기 :

identical(t(apply(funPartition(10^4), 2, rev)), 
      comboGeneral(0:100,25,TRUE,"sum","==",100,10^4)) 
[1] TRUE 

Answer 2

다음은 단일 대상 행렬을 생성하는 함수입니다. 가장 효율적인 방법은 아닐 수 있습니다. 아주 많이 실행하면 모두의 가능한 조합 만 얻을 수 있습니다. lapply()을 rep(5, num) 이상으로 사용하면 num을 생성 할 수 있습니다.

norm100 <- function(n=5){ 

    # generate some random values 
    vec <- sample(0:100, size=n^2) 

    # put them in a matrix, normalizing to 100 and rounding 
    mat <- matrix(round((vec/sum(vec)) * 100), nrow=n) 

    # find out how much the rounding makes us deviate from 100 
    off_by <- sum(mat) - 100 

    # get a random matrix element index 
    modify_idx <- sample(length(mat), 1) 

    # if adjusting by `off_by` would put us out of the target interval, try again 
    while ((mat[modify_idx] - off_by) < 0 | (mat[modify_idx] - off_by) > 100){ 
    modify_idx <- sample(length(mat), 1) 
    } 

    # once we have one (usually on the first shot), adjust so that mat sums to 100 
    mat[modify_idx] <- mat[modify_idx] - off_by 
    return(mat) 
} 

runs <- 1000 
matrices <- lapply(rep(5, runs), norm100) 

나는 심지어 10 만 몇 실행 후 중복 된이라도하지 않은,하지만 당신이 할 경우, 당신은 단지 속는 항상 던져 수 있습니다.