CODEWITHSUNDEEP
r
Hugo van Kessel
Hugo van Kessel

Reputation: 59

sapply to create unique permutations without overlap

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.

Upvotes: 2

Views: 168

Answers (4)

GKi
GKi

Reputation: 39727

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

Upvotes: 3

G. Grothendieck
G. Grothendieck

Reputation: 270268

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

Upvotes: 3

elielink
elielink

Reputation: 1202

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

Upvotes: 1

Yuriy Saraykin
Yuriy Saraykin

Reputation: 8880

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

Upvotes: 2

Related Questions