9

Suppose I have an R vector of unique elements such as x <- c(1,2,3,4,5).

Is there a function to give me a list of all possible partitions of this vector x? I guess each partition would be a list of vectors, where each element in x belongs to one of the vectors. I want all possible partitions into any number of sets of any size.

(I think the number of such partitions is something like 2^n * n!, where n is the number of unique elements. I will probably not be using this function on vectors with more than 4 unique elements.)

Ryan C. Thompson
  • 38,976
  • 28
  • 92
  • 152
  • Your estimate seems to be too large. Call K the number of partitions. It is obvious that K(1) = 1 and K(2) = 2. You now have the relation: for N > 2, K(N) = 1 + N * (K(N - 1)). That is, consider the set of all of the elements, and then each set, with one particular element removed. This also leads to an algorithm for construction of the partitions. – Matthew Lundberg May 19 '12 at 02:38
  • The value of K(N) for N>1 would seem to depend on whether order of the partitions and order of the elements within the partitions matter. Would you provide your expected results for N=2 and N=3? – BenBarnes May 19 '12 at 13:36

2 Answers2

12

Here's a solution that will get you a complete list of partitions, each one of which is represented as a list of vectors. Since a list of lists is pretty ugly when printed to the screen, I've also shown you how to get a more nicely printed object.

library(partitions)

x <- c(2,4,6)       # Substitute the vector for which you want partitions 
parts <- listParts(length(x))
out <- rapply(parts, function(ii) x[ii], how="replace")

# This step is for cosmetic purposes only. It allows you to take advantage of
# the `print.equivalence` print method when printing the object to a console 
for(i in seq_along(out)) class(out[[i]]) <- c("list", "equivalence")
out
[[1]]
[1] (2,4,6)

[[2]]
[1] (2,6)(4)

[[3]]
[1] (2,4)(6)

[[4]]
[1] (4,6)(2)

[[5]]
[1] (2)(4)(6)

See also setparts() in the same package for a more compact way to represent the same set of partitions.

Josh O'Brien
  • 154,425
  • 26
  • 353
  • 447
0

Does this give you what you are looking for,

install.packages("gregmisc", dependencies = TRUE)
library(gregmisc)

x <- c(1,2,3,4,5)
for(i in 1:length(x)) {
print(combinations(5,i,x,repeats=TRUE))
}
Eric Fail
  • 7,757
  • 6
  • 65
  • 120