0

I am trying to find a way to efficiently use permutations of a vector in R without blowing up my computer. This is what I am trying to do:

n = 3 # I would need n>1000 instead, this is just to show what I am trying to achieve
t = 3

library(gtools)
m <- permutations(n = n, r = t, repeats.allowed = F, v = 1:n)
mm <- as.numeric(m)
df = data.frame()
for (i in 1:nrow(m)) {
    mat <- matrix(0, nrow = ncol(m), ncol = n)
    idx = m[i,]
    mat[cbind(seq_along(idx), idx)] = 1
    df = rbind(df, mat)
}

However using permutations, it is too time/memory consuming to work with large n (e.g. >1000). It looks like using "sample" is a great solution (proposed here):

v = 1:n
N <- t(replicate(length(v)^4, sample(v, t)))
# compare with: permutations(n = n, r = t, repeats.allowed = F, v = 1:n)
sum(duplicated(N))
m <- N[!(duplicated(N)), ] # then continue with code above

However, I am still unsure about the number of samples to take to be sure to cover all the possibilities. Does anybody have any ideas on number of samples, or how to make sure that all possibilities are covered? Thank you!

user971102
  • 3,005
  • 4
  • 30
  • 37
  • So you want to get all t lengthed permutations of the vector 1:1000? Do you know that there (1000!/(1000-t)!) ~= 1 billion permutations if t = 3? What is your goal, I either misunderstand the question or you misunderstand the scale of your problem. – bmrn Jan 22 '18 at 03:26
  • I am trying to get all combinations of arrays of t rows and n columns, where there is only 1 value that is non-zero for each row. For example, for t = 3 and n = 3, I am trying to get 6 arrays with these vectors for each row: 1. (1,0,0),(0,1,0),(0,0,1); 2. (1,0,0),(0,0,1)(0,1,0); 3.(0,1,0),(1,0,0),(0,0,1); 4.(0,1,0),(0,0,1),(1,0,0); 5. (0,0,1),(1,0,0),(0,1,0); 6.(0,0,1),(0,1,0),(1,0,0) – user971102 Jan 22 '18 at 04:11
  • Can I take from this example that you also require inly one non zero value per column? (Otherwise for example you could have 7.(1,0,0),(1,0,0),(0,1,0)). – bmrn Jan 22 '18 at 05:52
  • 1
    You decide a position to place the one on the first row. 1000 options, then on the second row you have 999 options since you can't place it in the same position as the first row. Then similarly you have 998 position to choose from on the third row. This is `1000 * 999 * 998` ( `= 1000!/(1000-3)!`) =~ 1 billion different possibilities for n = 1000, t = 3. Permutations can really get away from you, this is why neither of us will win the lottery. – bmrn Jan 22 '18 at 06:11

0 Answers0