Time to get another concept under my belt, combinations and permutations. While I'm at it, I will examine combinations and permutations in R. As you may recall from school, a **combination** does not take into account the order, whereas a **permutation** does. Using the example from my favourite website as of late, mathsisfun.com:

- A fruit salad is a
**combination**of apples, bananas and grapes, since it's the same fruit salad regardless of the order of fruits - To open a safe you need the right order of numbers, thus the code is a
**permutation**

As a matter of fact, a permutation is an ordered combination. There are basically two types of permutations, with repetition (or replacement) and without repetition (without replacement).

### Permutations with repetition

The number of permutations with repetition (or with replacement) is simply calculated by:

where n is the number of things to choose from, r number of times.

For example, you have a urn with a red, blue and black ball. If you choose two balls with replacement/repetition, there are permutations: {red, red}, {red, blue}, {red, black}, {blue, red}, {blue, blue}, {blue, black}, {black, red}, {black, blue}, and {black, black}. In R:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

#install if necessary | |

install.packages('gtools') | |

#load library | |

library(gtools) | |

#urn with 3 balls | |

x <- c('red', 'blue', 'black') | |

#pick 2 balls from the urn with replacement | |

#get all permutations | |

permutations(n=3,r=2,v=x,repeats.allowed=T) | |

# [,1] [,2] | |

# [1,] "black" "black" | |

# [2,] "black" "blue" | |

# [3,] "black" "red" | |

# [4,] "blue" "black" | |

# [5,] "blue" "blue" | |

# [6,] "blue" "red" | |

# [7,] "red" "black" | |

# [8,] "red" "blue" | |

# [9,] "red" "red" | |

#number of permutations | |

nrow(permutations(n=3,r=2,v=x,repeats.allowed=T)) | |

#[1] 9 |

A biological example of this are all the possible codon permutations. We have 4 choices (A, C, G, and T) and we are choosing 3 nucleotides: (though some permutations code for the same amino acid). How about the number of 11-mers that are possible: . For miRNAs of size 21, there are possible miRNAs, but since the majority of these 21-mers are probably not biologically relevant or even possible, they most likely don't exist.

### Permutations without repetition

Calculating permutations without repetition/replacement, just means that for cases where r > 1, n gets smaller after each pick. For example, if we choose two balls from the urn with the red, blue, and black ball but without repetition/replacement, the first pick has 3 choices and the second pick has 2 choices: {red, blue}, {red, black}, {blue, red}, {blue, black}, {black, red} and {black, blue}. In R:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

#install if necessary | |

install.packages('gtools') | |

#load library | |

library(gtools) | |

#urn with 3 balls | |

x <- c('red', 'blue', 'black') | |

#pick 2 balls from the urn with replacement | |

#get all permutations | |

permutations(n=3,r=2,v=x) | |

# [,1] [,2] | |

#[1,] "black" "blue" | |

#[2,] "black" "red" | |

#[3,] "blue" "black" | |

#[4,] "blue" "red" | |

#[5,] "red" "black" | |

#[6,] "red" "blue" | |

#number of permutations | |

nrow(permutations(n=3,r=2,v=x)) | |

#[1] 6 |

Let's use an example with more choices, say choosing pool balls. If we chose 3 balls without replacement (out of a total of 16), the number of permutations would be:

How do we reach a formula for this? If we chose all 16 balls, there are this many permutations:

Since we want , we can perform this division:

which is The formula is: the total number of permutations without replacement for divided by the factorial of the subtraction of the total number of possible choices () and the number of choices we make (); note that :

I wrote this formula as a function in R:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

perm_without_replacement <- function(n, r){ | |

return(factorial(n)/factorial(n - r)) | |

} | |

#16 choices, choose 16 | |

perm_without_replacement(16,16) | |

#[1] 2.092279e+13 | |

#16 choices, choose 3 | |

perm_without_replacement(16,3) | |

#[1] 3360 |

### Combinations without repetition

By now you've probably heard of induced Pluripotent Stem Cells (iPSCs), which are a type of pluripotent stem cell artificially derived from a non-pluripotent cell through the forced expression of four specific transcription factors (TFs). This discovery was made by Yamanaka-sensei and his team. Prior to the discovery, Yamanaka-sensei and his team investigated 24 TFs known to be important in early embryo development and tested different combinations of these TFs. How many combinations are there for a set of 4 TFs?

Since the TFs are used once, the number of combinations are without repetition/replacement and the order does not matter; all four TFs just need to be added. Since combinations are order agnostic, there will be less combinations than permutations under the same scenario. Let's calculate the number of permutations to get an upper bound:

As pointed out above, many of these permutations are the same combination. Actually, for 4 TFs, there are permutations that are the same combination. So we should reduce the number of permutations, by 24, to arrive at the number of combinations: which is In R, these is already a built in function for this called choose():

#calculate the number of combinations without replacement/repetition choose(n=24,k=4) [1] 10626

The formula, for the number of combinations without repetition/replacement, would be very similar to working out the number of permutations without repetition/replacement; it is simply the same formula but decreased by the number of size r permutations without replacement/repetition:

where n is the number of things to choose from, choosing r of them. For the above example:

### Combinations with repetition

This is actually quite complicated to figure out intuitively. To get started, let's use the urn with the 3 balls, a red, blue and black ball. If we choose 3 balls with replacement, the possible combinations are:

- 3 colours: {red, red, red}, {blue, blue, blue}, {black, black, black}
- 2 red: {red, red, blue}, {red, red, black}
- 2 blue: {blue, blue, red}, {blue, blue, black}
- 2 black: {black, black, red}, {black, black, blue}
- 1 of each: {red, blue, black}
- scenarios with 1 red or 1 blue or 1 black are redundant, i.e. already listed above

which equals 10 possible combinations. The first thing I thought about was, with repetition/replacement, how many permutations are there for choosing 3 balls in a urn with 3 balls?

How many combinations are there without repetition/replacement?

So the answer is in between 1 and 27 (it is 10) but the question is how do we remove the redundant combinations from the permutations with repetition (the 27 cases)?

On mathsisfun.com, they used a special technique to work this out. Instead of balls in a urn, they considered scoops of ice cream per customer order. Imagine, there are 3 tubs of ice cream in succession, chocolate, vanilla and strawberry and there is a robot that moves from left to right and can also perform scoops. If a customer orders 3 scoops of vanilla, the robot will move once to the right, make 3 scoops and then once to the right to reach the last tub. To represent this in symbols: -> S S S ->, where S = scoop and -> means move right once. If the customer ordered a Neapolitan ice cream, it would be S -> S -> S. So now the question is how many arrangements of scoops and arrows can we have? If we list them all out, where chocolate = c, vanilla = v, and strawberry = s:

**c, c, c**: S S S -> ->**c, c, v**: S S -> S ->**c, c, s**: S S -> -> S**v, v, v**: -> S S S ->**c, v, v**: S -> S S ->**v, v, s**: -> S S -> S**s, s, s**: -> -> S S S**c, s, s**: S -> -> S S**v, s, s**: -> S -> S S**c, v, s**: S -> S -> S

Notice that we have 3 scoops and 2 arrows each time. Asking for the number of arrangements of scoops and arrows is actually the same as asking for the number of combinations without repetition/replacement for n = 5 and r = 3:

However, for our original question we had n = 3 and r = 3; we need to make n = 5. It turns out that **r + (n - 1)** will give us the 5 (when n = 3 and r = 3). So we can substitute **r + (n - 1)** as n:

For our example of 3 scoops of ice cream from 3 tubs, the number of combinations with repetition is:

I wrote the function in R:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

comb_with_replacement <- function(n, r){ | |

return( factorial(n + r - 1) / (factorial(r) * factorial(n - 1)) ) | |

} | |

#have 3 elements, choosing 3 | |

comb_with_replacement(3,3) | |

#[1] 10 |

Now back to the four Yamanaka factors; if each TF is actually a discrete unit, where we can add the same TF one or more times (i.e. with repetition), such as {Sox2, Sox2, Sox2, Sox2}, how many combinations are there? Intuitively this number is > (number of combinations without repetition/replacement):

comb_with_replacement(24,4) [1] 17550

### Conclusions

I'm starting to learn things intuitively and not by rote, especially mathematical concepts. I may forget the formulae for the 4 scenarios above (ordered with repetition, ordered without repetition, order agnostic with repetition and order agnostic without repetition), but I can figure them out again because they make intuitive sense.

I decided to dedicate time to finally lock in the concepts of permutations and combinations in my head because there are so many applications of these concepts in everyday life and in biology (as I've tried to demonstrate). I have also written some functions for calculating combinations and permutations in R, and shown examples of using the gtools package to list out all possible permutations; I wrote the functions to replicate the formulae in R.

A note that Yamanaka-sensei, didn't actually go about checking all the combinations. As far as I'm aware, he used all 24 transcription factors and kept subtracting different TFs, i.e. deductive reasoning, to see which ones were important for the formation of iPSCs.

And lastly, maths is indeed fun!

### Further reading

Combinations and permutations on mathsisfun.com

Permutations and combinations (without repetition/replacement) on betterexplained.com

Another explanation of combinations with repetition/replacement.

This work is licensed under a Creative Commons

Attribution 4.0 International License.

Hei, thanks for this post. It really help me to pick a list of 5 stocks from a big-list of 50 stocks. (50 p 5) . Can you please help me with the code to get the combinations?

Regards,

Jagan

Hi Jagan,

try adapting this code to your own example:

Cheers,

Dave

I have a similar but different issue. I have 4 learners { ada, rf, svm, and nnet }.

So I am trying to average those learners to find the lowest error against my response.

So,

I would want to pass to a function these but I think I would have to do a sapply() for each row below.

c(ada,rf,svm,nnet) is 4!/4!

c(ada,rf,svm), c(ada, rf, nnet), c(ada, svm, nnet), c(rf, svm, nnet) is cuberoot (4^3)

c(ada,rf), c(ada,svm), c(ada,nnet), c(rf,svm), c(rf,nnet), c(svm, nnet) is (4!/2!) / 2

So, what is this? I want all of the unique sets possible out of 4 excluding the sets of 1. Unless I made an error there are 11 of them as described above.

How do you find these using the formulas above without backing into it?

Thinking about it, I realized what I have….I have 4^2 minus the(4) single sets and the empty set. DUH!

Hi?I found something interesting about the permutation and combination function, when I try this code below:

x <- c("id","A","B","C")

permutations(n=3,r=2,v=x)

I expected to get the result below:

[,1] [,2]

[1,] "id" "A"

[2,] "id" "B"

[3,] "A" "B"

[4,] "A" "C"

[5,] "B" "A"

[6,] "B" "C"

but I actually get was this:

[,1] [,2]

[1,] "A" "B"

[2,] "A" "C"

[3,] "B" "A"

[4,] "B" "C"

[5,] "C" "A"

[6,] "C" "B"

It's wired, isn't it? This function automatically ignore the "id", do you know why?

Your vector size is 4 but you set it to 3 (n=3). Use:

`x <- c("id","A","B","C"); permutations(n=4, r=2, v=x)`

Hi, thank you so much for the post.

I did get the combinations but I’m trying to figure out the way to apply those different combinations to a function and get the results from each combination. Is there any way to make R do that by itself instead of me putting all those combinations manually to get each result? Could you please help me with that?

Thanks!

Hanna

I’m sorry but I don’t understand your question.

Hello.

I want to write an R code to generate all distinct permutations of a list with a repeated characters in an efficient way. For example, let x<-c(1,1,2,2,3,4) then

library(permute)

unique(permn(x))

works, but it is very inefficient.

Hi,

This is a great post and as a follow up perhaps you could enlighten a doubt I have.

Would you be able to think of a solution in R to derive a dataframe with all different combinations from 2 large dataframes (100k rows x 2 columns)?

The data would be geographical coordinates and my idea is to run all these combinations between the points (each row of each data frame is a geo-point) to thereafter calculate distances.

Appreciate your thoughts.

Best regards

You have no idea how much you have helped by point me out to this concept and package!

I was struggling with a code and the answer was simple as a combination! Many thanks!

Please continue to do this amazing work you do!

I’m very glad that you have found this useful! I haven’t been blogging lately but thank you for the encouraging comment!