[R] help with apply, please

[Gabor Grothendieck]

On 11/19/05, Gabor Grothendieck <ggrothendieck at gmail.com> wrote:
> Try minizing 1'x subject to 1 >= x >= 0 and m'x >= 1 where m is your mtrx
> and ' means transpose.  It seems to give an integer solution, 1 0 1,
> with linear programming even in the absence of explicit integer
> constraints:
>
> library(lpSolve)
> lp("min", rep(1,3), rbind(t(mtrx), diag(3)), rep(c(">=", "<="), 4:3),
> rep(1,7))$solution

Just one after thought.  The constraint x <= 1 will not be active so,
eliminating it, the above can be reduced to:

lp("min", rep(1,3), rbind(t(mtrx)), rep(">=", 4), rep(1,4))$solution


>
>
>
> On 11/19/05, Adrian DUSA <adi at roda.ro> wrote:
> > Dear list,
> >
> > I have a problem with a toy example:
> > mtrx <- matrix(c(1,1,0,1,1,1,0,1,1,0,0,1), nrow=3)
> > rownames(ma) <- letters[1:3]
> >
> > I would like to determine which is the minimum combination of rows that
> > "covers" all columns with at least a 1.
> > None of the rows covers all columns; all three rows clearly covers all
> > columns, but there are simpler combinations (1st and the 3rd, or 2nd and 3rd)
> > which also covers all columns.
> >
> > I solved this problem by creating a second logical matrix which contains all
> > possible combinations of rows:
> > tt <- matrix(as.logical(c(1,0,0,0,1,0,0,0,1,1,1,0,1,0,1,0,1,1,1,1,1)), nrow=3)
> >
> > and then subset the first matrix and check if all columns are covered.
> > This solution, though, is highly inneficient and I am certain that a
> > combination of apply or something will do.
> >
> > ###########################
> >
> > possibles <- NULL
> > length.possibles <- NULL
> > ## I guess the minimum solution is has half the number of rows
> > guesstimate <- floor(nrow(tt)/2) + nrow(tt) %% 2
> > checked <- logical(nrow(tt))
> > repeat {
> >    ifelse(checked[guesstimate], break, checked[guesstimate] <- TRUE)
> >    partials <- as.matrix(tt[, colSums(tt) == guesstimate])
> >    layer.solution <- logical(ncol(partials))
> >
> >    for (j in 1:ncol(partials)) {
> >        if (length(which(colSums(mtrx[partials[, j], ]) > 0)) == ncol(mtrx)) {
> >            layer.solution[j] <- TRUE
> >        }
> >    }
> >    if (sum(layer.solution) == 0) {
> >        if (!is.null(possibles)) break
> >        guesstimate <- guesstimate + 1
> >    } else {
> >        for (j in which(layer.solution)) {
> >            possible.solution <- rownames(mtrx)[partials[, j]]
> >            possibles[[length(possibles) + 1]] <- possible.solution
> >            length.possibles <- c(length.possibles, length(possible.solution))
> >        }
> >        guesstimate <- guesstimate - 1
> >    }
> > }
> > final.solution <- possibles[which(length.possibles == min(length.possibles))]
> >
> > ###########################
> >
> > More explicitely (if useful) it is about reducing a prime implicants chart in
> > a Quine-McCluskey boolean minimisation algorithm. I tried following the
> > original algorithm applying row dominance and column dominance, but (as I am
> > not a computer scientist), I am unable to apply it.
> >
> > If you have a better solution for this, I would be gratefull if you'd share
> > it.
> > Thank you in advance,
> > Adrian
> >
> > --
> > Adrian DUSA
> > Romanian Social Data Archive
> > 1, Schitu Magureanu Bd
> > 050025 Bucharest sector 5
> > Romania
> > Tel./Fax: +40 21 3126618 \
> >          +40 21 3120210 / int.101
> >
> > ______________________________________________
> > R-help at stat.math.ethz.ch mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
> >
>