Randy Lai Randy Lai - 2 months ago 5
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.

Answer

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" 
Comments