2

I am trying to create a function that will do the following:

input: 1:3
output: 1 2 3 2 3 1 3 1 2

In this way i want to generate all permutations of the input where the elements never overlap for each given index

1 2 3 and  2 3 1 and 3 1 2

I have come as far as:

sapply(1:4,(function(i){paste0(i,i+1,i+2,i+3)}))

but this does not generate the output i am looking for.

Behnam Hedayat
  • 837
  • 4
  • 18
Hugo van Kessel
  • 59
  • 2
  • Have also a look at [Generating all distinct permutations of a list in R](https://stackoverflow.com/q/11095992/10488504). – GKi May 26 '21 at 14:41

4 Answers4

3

Reading your comment in looks like you can use matrix to generate the wanted numbers like:

n <- 2
matrix(1:n, n+1, n)[1:n,]
#     [,1] [,2]
#[1,]    1    2
#[2,]    2    1

n <- 3
matrix(1:n, n+1, n)[1:n,]
#     [,1] [,2] [,3]
#[1,]    1    2    3
#[2,]    2    3    1
#[3,]    3    1    2

n <- 4
matrix(1:n, n+1, n)[1:n,]
#     [,1] [,2] [,3] [,4]
#[1,]    1    2    3    4
#[2,]    2    3    4    1
#[3,]    3    4    1    2
#[4,]    4    1    2    3

n <- 5
matrix(1:n, n+1, n)[1:n,]
#     [,1] [,2] [,3] [,4] [,5]
#[1,]    1    2    3    4    5
#[2,]    2    3    4    5    1
#[3,]    3    4    5    1    2
#[4,]    4    5    1    2    3
#[5,]    5    1    2    3    4

My first answer to generate all permutations in base using expand.grid was:

x <- 1:3
do.call(expand.grid, lapply(x, \(i) x)) ->.
  .[apply(., 1, anyDuplicated) == 0,]
#   Var1 Var2 Var3
#6     3    2    1
#8     2    3    1
#12    3    1    2
#16    1    3    2
#20    2    1    3
#22    1    2    3
GKi
  • 37,245
  • 2
  • 26
  • 48
3

I assume that problem is that we are given n and we want a vector containing 1:n followed by each permutation of 1:n for which the ith element of each such permutation is not i. We generate all permutations and then eliminate those for which the ith position equals i for all i in 1:n, i.e. if P is permutation of 1:n then we only accept it if all(P != 1:n) is TRUE. The calculation below will get large very quickly but for small n it should be ok.

library(RcppAlgos)

n <- 2
p <- permuteGeneral(n)
c(cbind(1:n, t(p[apply(t(p) != 1:n, 2, all), , drop = FALSE])))
## [1] 1 2 2 1

n <- 3
p <- permuteGeneral(n)
c(cbind(1:n, t(p[apply(t(p) != 1:n, 2, all), , drop = FALSE])))
## [1] 1 2 3 2 3 1 3 1 2

n <- 4
p <- permuteGeneral(n)
c(cbind(1:n, t(p[apply(t(p) != 1:n, 2, all), , drop = FALSE])))
## [1] 1 2 3 4 2 1 4 3 2 3 4 1 2 4 1 3 3 1 4 2 3 4 1 2 3 4 2 1 4 1 2 3 4 3 1 2 4 3 2 1
G. Grothendieck
  • 254,981
  • 17
  • 203
  • 341
  • Hi! for n =2 and n =3 this function works for me. the desired output for n=4 would be the sequence 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 , so 1234 2341 3412 4123 column wise there is no overlap between numbers i now realize that my explanation was not clear (i find it quite hard to formulate correctly but i hope it is clear now) n=2 12 21 n= 3 123 231 312 n= 4 1234 2341 3412 4123 n= 5 12345 23451 34512 45123 51234 – Hugo van Kessel May 28 '21 at 09:42
  • However, your approach inspired me! n = 5 cbind(matrix(rep(1:n, n-1), ncol = n-1, byrow = T), rev(1:n)) this works for me! Thanks! – Hugo van Kessel May 28 '21 at 09:58
  • @Hugo, The code in your comment happens to give the correct answer for n=2 and n=3 but in general will only give n-1 permutations which cannot be correct. – G. Grothendieck May 28 '21 at 11:24
  • I understand! i did not formulate my problem correctly but i have my answer now! Thank you! – Hugo van Kessel May 28 '21 at 16:09
2

if I understand correctly

  combinat::permn(x = 1:3)

[[1]]
[1] 1 2 3

[[2]]
[1] 1 3 2

[[3]]
[1] 3 1 2

[[4]]
[1] 3 2 1

[[5]]
[1] 2 3 1

[[6]]
[1] 2 1 3
Yuriy Saraykin
  • 8,390
  • 1
  • 7
  • 14
1

You can also use the permutations function from gtools package:

permutations(n=3,r = 3,v = 1:3)

The output is

     [,1] [,2] [,3]
[1,]    1    2    3
[2,]    1    3    2
[3,]    2    1    3
[4,]    2    3    1
[5,]    3    1    2
[6,]    3    2    1
elielink
  • 1,174
  • 1
  • 10
  • 22