How to calculate combination and permutation in R?
You can use the combinat
package with R 2.13:
install.packages("combinat")
require(combinat)
permn(3)
combn(3, 2)
If you want to know the number of combination/permutations, then check the size of the result, e.g.:
length(permn(3))
dim(combn(3,2))[2]
R: combinatorics, number of permutations for one combination
The number of permutations of a
indistinguishable copies of item 1, b
of item 2, c
of item 3, where a + b + c = N
, is N! / (a! b! c!)
.
For example if you had (a,b,c) = (3,1,1)
then there are 5!/(3! 1! 1!) = 20
arrangements.
c b a a a b a c a a a b a a c a a c a b
c a b a a b a a c a a c b a a a a b c a
c a a b a b a a a c a c a b a a a b a c
c a a a b a b c a a a c a a b a a a b c
b c a a a a b a c a a a c b a a a a c b
In general, we can calculate the number as follows
nperm<-function(...) {
args<-as.numeric(list(...));
num<-lfactorial(sum(args));
den<-sum(lfactorial(args));
return(round(exp(num-den)));
}
So, e.g.,
x<-expand.grid(0:5,0:5,0:5)
x<-x[rowSums(x)==5,]
x[,"nperm"]<-apply(x,1,function(x) do.call(nperm,as.list(x)))
Var1 Var2 Var3 nperm
5 0 0 1
4 1 0 5
3 2 0 10
2 3 0 10
1 4 0 5
0 5 0 1
4 0 1 5
3 1 1 20
2 2 1 30
1 3 1 20
0 4 1 5
3 0 2 10
2 1 2 30
1 2 2 30
0 3 2 10
2 0 3 10
1 1 3 20
0 2 3 10
1 0 4 5
0 1 4 5
0 0 5 1
And sum(x[,"nperm"]) == 243
, as expected.
Calculate large number of permutations in R
cmb<-expand.grid(1:nrow(A),1:nrow(B))
cbind(A[cmb[,1],],B[cmb[,2],])
Unlike Andre's solution, this won't create combinations of the columns within each of A and B (his creates 81 rows, whereas for this sample, only 9 are desired). Not sure if this will work for your larger dataset, though.
How to generate permutations or combinations of object in R?
EDIT: I have updated the answer to use a more efficient package arrangements
Getting start of using arrangement
arrangements contains some efficient generators and iterators for permutations and combinations. It has been demonstrated that arrangements
outperforms most of the existing packages of similar kind. Some benchmarks could be found here.
Here are the answers to the above questions
# 1) combinations: without replacement: distinct items
combinations(5, 2)
[,1] [,2]
[1,] 1 2
[2,] 1 3
[3,] 1 4
[4,] 1 5
[5,] 2 3
[6,] 2 4
[7,] 2 5
[8,] 3 4
[9,] 3 5
[10,] 4 5
# 2) combinations: with replacement: distinct items
combinations(5, 2, replace=TRUE)
[,1] [,2]
[1,] 1 1
[2,] 1 2
[3,] 1 3
[4,] 1 4
[5,] 1 5
[6,] 2 2
[7,] 2 3
[8,] 2 4
[9,] 2 5
[10,] 3 3
[11,] 3 4
[12,] 3 5
[13,] 4 4
[14,] 4 5
[15,] 5 5
# 3) combinations: without replacement: non distinct items
combinations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2)
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "c"
# 4) combinations: with replacement: non distinct items
combinations(x = c("a", "b", "c"), k = 2, replace = TRUE) # as `freq` does not matter
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "b"
[5,] "b" "c"
[6,] "c" "c"
# 5) permutations: without replacement: distinct items
permutations(5, 2)
[,1] [,2]
[1,] 1 2
[2,] 1 3
[3,] 1 4
[4,] 1 5
[5,] 2 1
[6,] 2 3
[7,] 2 4
[8,] 2 5
[9,] 3 1
[10,] 3 2
[11,] 3 4
[12,] 3 5
[13,] 4 1
[14,] 4 2
[15,] 4 3
[16,] 4 5
[17,] 5 1
[18,] 5 2
[19,] 5 3
[20,] 5 4
# 6) permutations: with replacement: distinct items
permutations(5, 2, replace = TRUE)
[,1] [,2]
[1,] 1 1
[2,] 1 2
[3,] 1 3
[4,] 1 4
[5,] 1 5
[6,] 2 1
[7,] 2 2
[8,] 2 3
[9,] 2 4
[10,] 2 5
[11,] 3 1
[12,] 3 2
[13,] 3 3
[14,] 3 4
[15,] 3 5
[16,] 4 1
[17,] 4 2
[18,] 4 3
[19,] 4 4
[20,] 4 5
[21,] 5 1
[22,] 5 2
[23,] 5 3
[24,] 5 4
[25,] 5 5
# 7) permutations: without replacement: non distinct items
permutations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2)
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "a"
[5,] "b" "c"
[6,] "c" "a"
[7,] "c" "b"
# 8) permutations: with replacement: non distinct items
permutations(x = c("a", "b", "c"), k = 2, replace = TRUE) # as `freq` doesn't matter
[,1] [,2]
[1,] "a" "a"
[2,] "a" "b"
[3,] "a" "c"
[4,] "b" "a"
[5,] "b" "b"
[6,] "b" "c"
[7,] "c" "a"
[8,] "c" "b"
[9,] "c" "c"
Compare to other packages
There are few advantages of using arrangements
over the existing packages.
Integral framework: you don't have to use different packages for different methods.
It is very efficient. See https://randy3k.github.io/arrangements/articles/benchmark.html for some benchmarks.
It is memory efficient, it is able to generate all 13! permutation of 1 to 13, existing packages will fail to do so because of the limitation of matrix size. The
getnext()
method of the iterators allow users to get the arrangements one by one.The generated arrangements are in dictionary order which may be desired for some users.
Multiple combination and permutation in r
For the sake of shorter explanation and more universal (as you mentioned number of rows can be grater that 10) I'm proposing following logic which you can implement yourself:
At the beginning, initial settings.
n <- 10
k <- 3
df <- as.data.frame( lapply(1:n, function(x) x <- k:1 ) )
Code below creates all unique combinations of 10-element set where order doesn't matter.
all <- as.matrix( expand.grid(df) )
all_sorted <- t( apply(all, 1, sort) )
all_sorted_unique <- unique(all_sorted)
In 10-elements set, all unique elements must appear
exclude_if_not_all <-
which(
apply(all_sorted_unique, 1,
function(x) length(unique(x))!=3)
)
t( all_sorted_unique[-exclude_if_not_all,] )
Result as expected.
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26] [,27] [,28] [,29] [,30] [,31] [,32] [,33] [,34] [,35] [,36]
[1,] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[2,] 2 2 1 2 1 1 2 1 1 1 2 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1
[3,] 3 2 2 2 2 1 2 2 1 1 2 2 1 1 1 2 2 1 1 1 1 2 2 1 1 1 1 1 2 2 1 1 1 1 1 1
[4,] 3 3 3 2 2 2 2 2 2 1 2 2 2 1 1 2 2 2 1 1 1 2 2 2 1 1 1 1 2 2 2 1 1 1 1 1
[5,] 3 3 3 3 3 3 2 2 2 2 2 2 2 2 1 2 2 2 2 1 1 2 2 2 2 1 1 1 2 2 2 2 1 1 1 1
[6,] 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 1 1 2 2 2 2 2 1 1 1
[7,] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 1 1
[8,] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
[9,] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
[10,] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
What you need to do right now is to bind only this matrix to your initial data.
All in Function
customPermutation <- function(n, k){
df <- as.data.frame( lapply(1:n, function(x) x <- 1:k ) )
all <- as.matrix( expand.grid(df) )
all_sorted <- t( apply(all, 1, sort) )
all_sorted_unique <- unique(all_sorted)
exclude_if_not_all <- which( apply(all_sorted_unique, 1, function(x) length(unique(x))!=3) )
t( all_sorted_unique[-exclude_if_not_all,] )
}
How to calculate the product from combinations of several vectors in R?
The expand.grid
solution is OK, but in mathematics there is an elegant Kronecker product.
R has a function kronecker
, but it takes two vectors at a time, so we need Reduce
for a recursive application:
oo <- Reduce(kronecker, list(a, b, c, d))
Alternatively, use outer
(the workhorse of kronecker
):
rr <- Reduce(outer, list(a, b, c, d))
This is more user-friendly, as rr[i, j, u, v]
gives you a[i] * b[j] * c[u] * d[v]
.
Remark 1
Note that elements in oo
and rr
differ in order. Because for two vectors a
and b
:
kronecker(a, b) ## a[1] * b, a[2] * b ...
outer(a, b) ## a * b[1], a * b[2] ...
Thus the following use of kronecker
produces a result identical to rr
.
zz <- Reduce(kronecker, list(d, c, b, a))
dim(zz) <- c(length(a), length(b), length(c), length(d))
Remark 2
The method can be adapted to do a[i] + b[j] + c[u] + d[v]
, by replacing the default operation "*"
in outer
and kronecker
to "+"
. For example:
Reduce(function (x, y) outer(x, y, "+"), list(a, b, c, d))
Remark 3
johannes's answer can be improved. That row-wise application of apply
is a performance killer. We can do the following to get a result consistent with rr
.
xx <- Reduce("*", expand.grid(a, b, c, d))
dim(xx) <- c(length(a), length(b), length(c), length(d))
Related Topics
Creating a New Variable from a Lookup Table
Display Custom Image as Geom_Point
How to Search for "R" Materials
Controlling Line Color and Line Type in Ggplot Legend
Dealing with True, False, Na and Nan
Concatenate Unique Strings After Groupby in R
Reverse Order of Discrete Y Axis in Ggplot2
Perform a Semi-Join with Data.Table
Subsetting Data.Table Using Variables with Same Name as Column
Floating Point Less-Than-Equal Comparisons After Addition and Substraction
Create Dynamic Number of Input Elements with R/Shiny
Rolling Join on Data.Table with Duplicate Keys
Export a List into a CSV or Txt File in R
R Split Numeric Vector at Position
The Cause of "Bad Magic Number" Error When Loading a Workspace and How to Avoid It