R: Матрица с colSums и rowSum, ограниченная 2 векторами - PullRequest
Новая
       34

R: Матрица с colSums и rowSum, ограниченная 2 векторами

0 голосов
/ 26 марта 2012

Есть ли более элегантный (без кода) способ поиска матрицы OUT,

с colSums (OUT) <= a и rowSums (OUT) <= b, </p>

при заданном ORD =порядок заполнения

сумма (OUT) -> максимальная

Судоку, как проблема, (числа не уникальны, и порядок заполнения задан, поэтому на самом деле не судоку).Я чувствую, что есть более простое решение этой проблемы. 

a <- c(4,2,1)
b <- c(3,2,2)
ORD <- matrix(c(1,5,6,8,2,9,7,4,3),ncol=3)

MIN <- outer(a,b,pmin)
OUT <- matrix(0,ncol=ncol(ORD),nrow=nrow(ORD))
L <- cbind(as.vector(row(ORD)),as.vector(col(ORD)))[order(ORD),]
for( i in 1:nrow(L)){
  r <- L[i,1]
  c <- L[i,2]
  OUT[r,c] <- min(a[c],b[r])
  a[c] <- max(a[c] - OUT[r,c],0)
  b[r] <- max(b[r] - OUT[r,c],0)
}

OUT

Редактировать: Спасибо!И наконец я закончил с этим (довольно длинный код для очень простой задачи;): 

cs <- c(4,2,1)
rs <- c(3,3,2)
ORD <- matrix(c(1,5,6,8,2,9,7,4,3),ncol=length(cs),byrow=T)

OUT <- matrix(0, nrow = length(rs), ncol = length(cs))
ROW <- row(OUT)
COL <- col(OUT)
for (i in order(ORD)){
  r <- ROW[i]
  c <- COL[i]
  k <- min(cs[c],rs[r])
  if(k>0){
    OUT[i] <- k
    cs[c] <- cs[c] - k
    rs[r] <- rs[r] - k
  }
  if(all(cs==0) | (all(rs==0)))
    break
}

Ответы [ 2 ]

1 голос
/ 26 марта 2012

Не изменяя ваш алгоритм, я могу сделать его немного короче: 

OUT <- matrix(0, nrow = length(b), ncol = length(a))
ROW <- row(OUT)
COL <- col(OUT)
for (i in order(ORD)) {
  r <- ROW[i]
  c <- COL[i]
  OUT[i] <- min(a[c], b[r])
  a[c] <- max(a[c] - OUT[i], 0)
  b[r] <- max(b[r] - OUT[i], 0)
}

Если вас волнует только количество строк, вы можете сделать: 

OUT <- matrix(0, nrow = length(b), ncol = length(a))
for (i in order(ORD)) {
  OUT[i] <- min(a[col(OUT)[i]], b[row(OUT)[i]])
  a[col(OUT)[i]] <- max(a[col(OUT)[i]] - OUT[i], 0)
  b[row(OUT)[i]] <- max(b[row(OUT)[i]] - OUT[i], 0)
}

, ноЯ очень рекомендую первую версию для лучшей читаемости.

0 голосов
/ 26 марта 2012

Вот элегантный (по вашему определению), но потенциально медленный способ, который использует поток управления для получения такой матрицы грубой силой.

while({OUT <- matrix(sample(0:max(a, b), 9, T), 3)
 !all(colSums(OUT) <= a & rowSums(OUT) <= b)}) {}

OUT
...