Generating Possible Sequences in R

Question

I am trying to solve the following problem in R. Generically, given a sequence [a,b], I am to generate lists from this sequence that have a length n, whose elements pairwise at least have a difference of d.

I was thinking of using seq() but you can only create evenly-spaced sequences using this function.

I think you'll get more (any?) response if you start with something more clearly defined. Can you provide a concrete example of `[a,b]`, some candidate sequences, and why some pass and some fail? References for reproducible questions: https://stackoverflow.com/questions/5963269, https://stackoverflow.com/help/mcve, and https://stackoverflow.com/tags/r/info. — r2evans, Feb 03 '19 at 00:12
All sequences or just random realizations? Are a, b, d real numbers? Integers? — Julius Vainora, Feb 03 '19 at 00:43

zacdav · Accepted Answer · 2019-02-04T04:50:36.247

This may be what you are after, generate all permutations of the possible different values that could exist in the sequence for size n and then check which satisfy your requirements of having their terminal value be b.

This is quite intensive and slow for larger vectors, but should return all possible valid sequences (unless I've made a mistake).

# sequence length of n which includes a, b
# therefore need to find n - 1 values (then check that last val of cumsum == b)
#   vals must be greater than or equal to d
#   vals have upper bound is if all but one value was d, b - ((n - 1) * d)
library(gtools)
library(matrixStats)

# parameters
a = 1
b = 20
n = 5
d = 2

# possible values that differences can be
poss_diffs <- d:(b - ((n - 1) * d))

# generate all possible permutations of differences
diff_perms_n <- permutations(n = length(poss_diffs), r = n - 1, v = poss_diffs)

# turn differences into sequences, add column for the a value
seqs_n <- matrixStats::rowCumsums(cbind(a, diff_perms_n))

# filter to only valid sequences, last column == b
valid_seqs <- seqs_n[seqs_n[, ncol(seqs_n)] == b, ]

# check that diffs are all greater than d
valid_seqs_diffs <- matrixStats::rowDiffs(valid_seqs)

print(head(valid_seqs))
print(head(valid_seqs_diffs))

# > print(head(valid_seqs))
# [,1] [,2] [,3] [,4] [,5]
# [1,]    1    3    6   10   20
# [2,]    1    3    6   11   20
# [3,]    1    3    6   12   20
# [4,]    1    3    6   14   20
# [5,]    1    3    6   15   20
# [6,]    1    3    6   16   20
# > print(head(valid_seqs_diffs))
# [,1] [,2] [,3] [,4]
# [1,]    2    3    4   10
# [2,]    2    3    5    9
# [3,]    2    3    6    8
# [4,]    2    3    8    6
# [5,]    2    3    9    5
# [6,]    2    3   10    4

Generating Possible Sequences in R

1 Answers1