Increase speed in finding "Ιncreasing dice roll sequences"

Question

The problem was How many sequences of 9 dice rolls are increasing (e.g. 223444556). Ok, I know the answer is given by choose(14,9) but i just wanted to play around with dplyr.

A fast but not elegant way:

library(tidyverse)

expand.grid(data.frame(matrix(rep(1:6,9),ncol=9))) %>% 
 filter(X1<=X2 & X2<=X3 &X3<=X4 &X4<=X5 &X5<=X6 &X6<=X7 &X7<=X8 &X8<=X9) %>% tally

I tried the following two alternatives (without explicit reference to variable names), but they're both very slow (and memory consuming). Can you help me optimize my code using tidyverse?

 expand_grid(!!!data.frame(matrix(rep(1:6,9),ncol=9))) %>% 
  rownames_to_column(var = "grp") %>% 
  mutate(grp = as.numeric(grp)) %>% 
  pivot_longer (cols=!grp) %>% 
  group_by(grp) %>% 
  mutate(prev = lag(value)) %>% 
  filter(!is.na(prev)) %>% 
  transmute(dif=value-prev) %>% 
  summarize(res = all(dif >=0)) %>% 
  group_by(res) %>% summarize(n=n())


 9 %>% 
    rerun(1:6) %>% crossing(!!!.,.name_repair = "minimal") %>%
    set_names(glue::glue('c{1:ncol(.)}')) %>% 
    rowwise() %>%
    mutate(asc = all(diff(c_across(cols = everything())>=0))) %>% 
    filter(asc==TRUE) %>% tally

This is also slow, but not memory consuming.

 9 %>% 
  rerun(1:6) %>% crossing(!!!.,.name_repair = "minimal")  %>% 
  set_names(glue::glue('c{1:ncol(.)}')) %>% 
  filter(pmap_lgl(.,~{
    if(all(list(...) %>% flatten_dbl() %>% diff() >=0)) return(TRUE) else return(FALSE)
  })) %>% tally

Answer 1

Here is another, more efficient solution, which uses a custom function get_nondecreasing_seqs, but does not use the tidyverse or dplyr.

get_nondecreasing_seqs <- function(digits, current_vector = numeric(0), allowed_nums) {
  res <- list()
  
  move_to_next <- function(new_digit, current_vector) {
    # Check if you have reached the desired length
    if (length(current_vector) == digits) {
      res[length(res) + 1] <<- list(current_vector)
    } else {
      # Try appending each allowed digit to the current vector
      for (next_digit in allowed_nums[allowed_nums >= new_digit]) {
        # Recursively call the function with the updated vector
        move_to_next(next_digit, c(current_vector, next_digit))
      }
    }
  }
  
  move_to_next(1, current_vector)
  
  return(res)
}

get_nondecreasing_seqs(9, allowed_nums = 1:6)

In the original approach using expand.grid and the tidyverse, all possible combinations of dice rolls were generated first, and then the non-decreasing sequences were filtered. This method could lead to a substantial memory overhead, especially when dealing with a large number of dice rolls, as it creates all combinations upfront.

In contrast, the custom function get_nondecreasing_seqs takes a more optimized approach. It dynamically builds the sequences while avoiding unnecessary combinations. It starts with the first digit and recursively explores only those paths that lead to non-decreasing sequences. This significantly reduces the number of iterations and memory usage, especially when the sequence length is large.

The efficiency gain comes from the fact that the function explores and appends valid digits to the current vector on the fly, eliminating the need to generate and store all possible combinations beforehand. This makes the custom function more resource-efficient and faster for calculating the non-decreasing sequences of dice rolls.