Function to compute permutations with repetition in R

Question

I want to generate all possible permutations of the vector

c(1,2,2,3,3)

in R. I used the following code:

library(combinat)
permn(c(1,2,2,3,3))

However, this function generates 5!=120 permutations, because it distinguishes the two 2 and the two 3. It should generate 5!/(2!*2!)=30 combinations.

This problem is solved using

unique(permn(c(1,2,2,3,3)))

However, I would like a function that gives the output of

unique(permn(c(1,2,2,3,3)))

directly, in a single function, not computing first all possible permutations via

permn(c(1,2,2,3,3))

Nothing seems to fit that bill even in the `combinat` or `permute` packages. This might be unusual enough that you need to code your own. The best name I can find for this is "permutations with duplicates", [there's a question here about algorithms to compute them](https://stackoverflow.com/q/11425070/903061), and I think some of the answers are in C++, so it might be pretty easy to port them over with `rcpp`. Good luck! — Gregor Thomas, Nov 10 '17 at 17:08
Unfortunately, "permutations with repetition" is used to describe contradictory things. For example, if you want to generate all possible three-digit numbers using the digits 0 through 9, you would generate permutations with repetition and get 1,000 of them. But if you're given a list of numbers, some of which are duplicated, then "permutations with repetition" means not treating the duplicates as unique. See, for example, https://www.ck12.org/book/CK-12-Basic-Probability-and-Statistics-Concepts-A-Full-Course/section/2.4/. Unfortunately, that link doesn't say how to generate them. — Jim Mischel, Nov 10 '17 at 18:12
If you want to implement it yourself, you could google "Knuth algorithm L". — Stéphane Laurent, Nov 10 '17 at 19:36

score 1 · Answer 1 · answered Nov 10 '17 at 19:51

You can get them with the iterpc package.

> x <- c(1, 2, 2, 3, 3)
> I <- iterpc(table(x), ordered=TRUE)
> getall(I)
      [,1] [,2] [,3] [,4] [,5]
 [1,]    1    2    2    3    3
 [2,]    1    2    3    2    3
 [3,]    1    2    3    3    2
 [4,]    1    3    2    2    3
 [5,]    1    3    2    3    2
 [6,]    1    3    3    2    2
 [7,]    2    1    2    3    3
 [8,]    2    1    3    2    3
 [9,]    2    1    3    3    2
[10,]    2    2    1    3    3
[11,]    2    2    3    1    3
[12,]    2    2    3    3    1
[13,]    2    3    1    2    3
[14,]    2    3    1    3    2
[15,]    2    3    2    1    3
[16,]    2    3    2    3    1
[17,]    2    3    3    1    2
[18,]    2    3    3    2    1
[19,]    3    1    2    2    3
[20,]    3    1    2    3    2
[21,]    3    1    3    2    2
[22,]    3    2    1    2    3
[23,]    3    2    1    3    2
[24,]    3    2    2    1    3
[25,]    3    2    2    3    1
[26,]    3    2    3    1    2
[27,]    3    2    3    2    1
[28,]    3    3    1    2    2
[29,]    3    3    2    1    2
[30,]    3    3    2    2    1

Function to compute permutations with repetition in R

1 Answers1