3

I'm trying to create an efficient function to generate all monotonically increasing permutations of a large vector. Obviously, reducing the outputs from expand.grid or gtools::permutations works, but only for smaller vectors.

Example:

x = 1:3

Desired output:

1, 1, 1
1, 1, 2
1, 1, 3
1, 2, 2
1, 2, 3
1, 3, 3
2, 2, 2
2, 2, 3
2, 3, 3
3, 3, 3

Any suggestions using base R or, existing packages with this capability?

EDIT: An ideal solution would avoid generating the complete set of permutations to then subset.

Fred Viole
  • 153
  • 7
  • Can you adjust your example desired output to display a permutation of length 2 (they are all currently length 3) – stevec Nov 25 '20 at 21:29
  • The permutations need to be of `length(x)`, but an additional argument for permutation length would be an improvement! – Fred Viole Nov 25 '20 at 21:45
  • When dealing with vectors of differing lengths, you need to think (carefully) about how you want to store them. For example, in your desired output above, would a vector of length 2 be displayed `1, 2, NA` ? – stevec Nov 25 '20 at 21:46
  • Thanks Steve, all output vectors would be of the same length according to the function argument, so I'm not sure why the 'NA' padding would be an issue. – Fred Viole Nov 25 '20 at 22:09
  • These are not permutations. These are simply combinations with repetition in lexicographical order. – Joseph Wood Nov 27 '20 at 15:27
  • I might misunderstand what you are looking for, but It looks like you are missing a few outputs as well; `(1, 1, 2), (1, 1, 3), (2, 2, 3)` – Joseph Wood Nov 27 '20 at 15:31
  • 1
    `arrangements` package is useful for this, thanks. – Fred Viole Nov 27 '20 at 17:21

2 Answers2

3

Using data.table this is fairly easy:

expand.monotonic <- function(x, len=length(x)){
    do.call(CJ, lapply(integer(len), function(...) x ))[
        eval(parse(text=paste0("V", 2:len, ">=", "V", 1:(len-1), collapse="&") )), ]
}
expand.monotonic(1:3)
   V1 V2 V3
 1:  1  1  1
 2:  1  1  2
 3:  1  1  3
 4:  1  2  2
 5:  1  2  3
 6:  1  3  3
 7:  2  2  2
 8:  2  2  3
 9:  2  3  3
10:  3  3  3

explanation:

First create a list containing the replicated vector len times, Use data.table::CJ to cross join all the vectors. And this is where the magic happens based on the len create an expression basically V2>=V1&V3>=V2 as V# is the default name for unnamed columns, and subset by the result of evaluating said expression.

parse(text=paste0("V", 2:len, ">=", "V", 1:(len-1), collapse="&") )
# expression(V2>=V1&V3>=V2)
Abdessabour Mtk
  • 3,895
  • 2
  • 14
  • 21
  • 1
    This is a very good solution using `data.table`! – Fred Viole Nov 25 '20 at 22:17
  • 1
    Thanks Abdessabour, I've edited the question to reflect the memory consideration as well. The `data.table` solution has a larger `object.size` than the `gtools::permutations` result and both are substantially larger than the final output. – Fred Viole Nov 25 '20 at 23:39
  • @FredViole I run through those errors when trying to benchmark, cross join eats up a lot of memory – Abdessabour Mtk Nov 25 '20 at 23:43
2

Here's some code which creates permutations with repeats allowed as in your example, and detects whether each permutation is monotonic

x <- 1:3

# Generate permutations of length x
out <- gtools::permutations(length(x), length(x), v = x, repeats.allowed=TRUE)

# Detect if they're monotonic
mono <- apply(out, 1, function(x) { all(x == cummax(x)) })


output_with_monotonic_label <- cbind(out, mono)

# output_with_monotonic_label
#             mono
#  [1,] 1 1 1    1
#  [2,] 1 1 2    1
#  [3,] 1 1 3    1
#  [4,] 1 2 1    0
#  [5,] 1 2 2    1
#  [6,] 1 2 3    1
#  [7,] 1 3 1    0
#  [8,] 1 3 2    0
#  [9,] 1 3 3    1
# [10,] 2 1 1    0
# ....
stevec
  • 41,291
  • 27
  • 223
  • 311