Sequences of randomly ordered numbers with unique neighbours-CodePudding

I want to create randomly ordered sequences of numbers (1 to 16) such as the following:

2 6 10 1 13 16 9 4 14 7 11 15 12 8 5 3

3 14 9 1 10 7 8 15 16 12 2 11 13 4 6 5

...

My limitation is that the neighbours of the numbers have to be unique across the sequences. So pairings like in the following example should be avoided.

4 6 3 14 11 13 10 5 12 16 9 2 15 8 7 1

1 15 9 14 3 6 8 5 7 2 10 13 12 16 4 11

Is there any algorithm or r-code/ package to solve this?

CodePudding user response：

You can do this with sample, lag and lead

set.seed(1)
x <- sample(1:16,16, replace=F)
x2 <- sample(1:16,16, replace=F)

prevs <- dplyr::lag(x)[-1]
nexts <- dplyr::lead(x)[-16]

prevs2<- dplyr::lag(x2)[-1]
nexts2 <- dplyr::lead(x2)[-16]

x
#>  [1]  9  4  7  1  2 14 12  3 13  5 11 10  6 15 16  8
x2
#>  [1]  9 15  5 14 16 12 13 10  2  8  6  1  4  3 11  7

any(prevs==prevs2 & nexts==nexts2)
#> [1] FALSE

^{Created on 2022-08-10 by the reprex package (v2.0.1)}

CodePudding user response：

Maybe, you can use simple rejection sampling. It quickly becomes inefficient if your samples are large.

Here I show it for two samples. Adjust for more samples on your own.

set.seed(42)
x <- sample(1:20, 20, replace = FALSE)
testx <- stats::filter(x, c(100, 1), sides = 1)[-1] 
#if you sample numbers with more than two digits, 
#replace 100 with a corresponding 10^n

n <- 1
repeat {
  message( "try ", n)
  n <- n   1
  y <- sample(1:20, 20, replace = FALSE)
  testy <- stats::filter(y, c(100, 1), sides = 1)[-1]
  if (all(outer(testx, testy, "-") != 0)) break
}
# try 1
# try 2
# try 3
# try 4
# try 5
# try 6
# try 7
x
#[1] 17  5  1 10  4  2 20 18  8  7 16  9 19  6 14 15 12  3 13 11
y
#[1] 17 18  2  6 20 16 15  4 12 19 10  7 13 14  8 11  1  9  5  3