[R] Help on a combinatorial task (lists?)

[Serguei Kaniovski]

Simple unlist() will not do. In case of repeated weights, unlike 
permutations of indices permn(1:length(w)) some permutations of weights 
are identical.

E.g. w <- c(3,2,2), permutations of indices c(1,2,3) and c(1,3,2) are 
undistinguishable.

I think I have corrected the algorithm, but now I stuck with a rather 
trivial list manipulation at the very end.

library(combinat)

w <- c(5,3,2,1)
i <- 1:length(w)
q <- 7

res <- sapply( permn(i), function(x) min(which(cumsum(w[x]) >=q)) )

Now I have the vector 'res' ( of size length(permn(i)) ), and I need to 
extract from each entry of the list produced by permn(i) the element 
with the index stored in 'res'.

E.g. the first three entries:

 > permn(i)[1:3]
[[1]]
[1] 1 2 3 4

[[2]]
[1] 1 2 4 3

[[3]]
[1] 1 4 2 3

...

 > res[1:3]
[1] 2 2 3

...

The answer should be 3, 4, 3 ...

Thanks again for you help!

Serguei K


jim holtman schrieb:
 > Does 'unlist' do it for you:
 >
 >> w <- c(3,3,2,1)  # vector of weights
 >> q <- 4  # theshold
 >>
 >> # computes which coordinate of w is decisive in each permutation
 >> res <- unlist(sapply( permn(w), function(x) which(w == 
x[min(which(cumsum(x) >=q))]) ))
 >>
 >> # complies the frequencies
 >> prop.table( tabulate( res ))
 > [1] 0.4 0.4 0.1 0.1
 >
 >
 > On Tue, Aug 11, 2009 at 7:03 AM, Serguei
 > Kaniovski<Serguei.Kaniovski at wifo.ac.at> wrote:
 >> Hello!
 >> I have the following combinatorial problem.
 >> Consider the cumulative sums of all permutations of a given weight 
vector
 >> 'w'. I need to know how often weight in a certain position brings the
 >> cumulative sums equal or above the given threshold 'q'. In other words,
 >> how often each weight is decisive in raising the cumulative sum 
above 'q'?
 >>
 >> Here is what I do:
 >>
 >> w <- c(3,2,1)  # vector of weights
 >> q <- 4  # theshold
 >>
 >> # computes which coordinate of w is decisive in each permutation
 >> res <- sapply( permn(w), function(x) which(w == x[min(which(cumsum(x) >=
 >> q))]) )
 >>
 >> # complies the frequencies
 >> prop.table( tabulate( res ))
 >>
 >>
 >> The problem I have is that when the weights are not unique, the which()
 >> function returns a list as opposed to a vector. I don’t know how to
 >> proceed when this happens, as tabulate does not work on lists.
 >>
 >> The answer, of course, should be that equal weights are “decisive” 
equally
 >> often.
 >>
 >>
 >> Can you help?
 >> Thanks a lot!
 >>
 >> Serguei Kaniovski
 >>
 >> ______________________________________________
 >> R-help at r-project.org mailing list
 >> https://stat.ethz.ch/mailman/listinfo/r-help
 >> PLEASE do read the posting guide 
http://www.R-project.org/posting-guide.html
 >> and provide commented, minimal, self-contained, reproducible code.
 >>
 >
 >
 >