Randy Lai - 1 year ago 157
R Question

# How to generate all permutations and combinations with/without replacement for distinct items and non distinct items (multisets)

In this thread, I am trying to include all the commonly asked questions and their answers here. I hope this will be useful for someone.

General question: How to generate sequences of

`r`
objects from
`n`
objects?

• combination vs permutation.

• with replacement vs without replacement.

• distinct items vs non distinct items (multisets).

There are in total
`2^3=8`
questions of this type.

[Update]

Josh O'Brien suggests that the 8 questions are related to twelvefold way. Indeed, the "distinct" questions are included in twelvefold way, while the "non distinct" questions are not included. Anyway, it is interesting to compare the 8 questions here with twelvefold way. See the comments for further readings.

## Existing packages

If you click here, you are able to see how to solve the problems by some existing packages (prior to the development of `iterpc`), such as `gtools`, `partitions`, `multicool`. However, I was not satified the fact that I have to use different packages for different problems of similar kind, so I decided to write my own packages.

There are few advantages of using `iterpc` over the existing packages.

1. Intergal framework: you don't have to use different packages for different methods.

2. It is fast, the whole implementation is written in c/c++. Compare to `gtools` which is
written in purely R, There is a significant gain.

3. It is memory efficient, it is able to generate all 13! permutation of 1 to 13, existing packages will fail to do so because the limitation of matrix size. The `getnext` function of `iterpc` enables you to get permutatioins/combinations one by one.

4. The generated sequences are in dictionary order.

## Getting start of using `iterpc`

I have written a package which is capable in solving the problems here. The package is written in c/c++, so should be very efficient. Please visit here for the details.

To show you how the package simplify the steps you need

``````# 1) combinations: without replacement: distinct items

I = iterpc(5, 2)
getall(I)

[,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

I = iterpc(5, 2, replace=TRUE)
getall(I)

[,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

x = c("a", "a", "b", "c")
I = iterpc(table(x), 2)
# or I = iterpc(c(2,1,1), 2, label=c("a", "b", "c"))
getall(I)

[,1] [,2]
[1,] "a"  "a"
[2,] "a"  "b"
[3,] "a"  "c"
[4,] "b"  "c"

# 4) combinations: with replacement: non distinct items

x = c("a", "a", "b", "c")
I = iterpc(table(x), 2, replace=TRUE)
# or I = iterpc(c(2,1,1), 2, label=c("a", "b", "c"), replace=TRUE)
getall(I)

[,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

I = iterpc(5, 2, ordered=TRUE)
getall(I)

[,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

I = iterpc(5, 2, replace=TRUE, ordered=TRUE)
getall(I)

[,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

x = c("a", "a", "b", "c")
I = iterpc(table(x), 2, ordered=TRUE)
# or I = iterpc(c(2,1,1), 2, label=c("a", "b", "c"), ordered=TRUE)
getall(I)

[,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

x = c("a", "a", "b", "c")
I = iterpc(table(x), 2, replace=TRUE, ordered=TRUE)
# or I = iterpc(c(2,1,1), 2, label=c("a", "b", "c"), replace=TRUE, ordered=TRUE)
getall(I)

[,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"
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download