How to Get a List of All Possible Partitions of a Vector in R

How can I get a list of all possible partitions of a vector in R?

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.

How can I get a list of all possible partition of a vector in R when the vector is large?

If like me you are not a superstar in combinatorics but you trust that partitions has it right, then at least you can make use of the package's code to compute the final number of partitions. Here I hacked the setparts function so, instead of the partitions themselves, it returns the number of partitions:

num.partitions <- function (x) {
    if (length(x) == 1) {
        if (x < 1) {
            stop("if single value, x must be >= 1")
        }
        else if (x == 1) {
            out <- 1
        }
        else return(Recall(parts(x)))
    }
    if (is.matrix(x)) {
        out <- sum(apply(x, 2, num.partitions))
    }
    else {
        x   <- sort(x[x > 0], decreasing = TRUE)
        out <- factorial(sum(x))/(prod(c(factorial(x), 
                                         factorial(table(x)))))
    }
    return(out)
}

Let's check that the function is returning the correct number of partitions:

num.partitions(restrictedparts(4, 3))
# [1] 14
ncol(setparts(restrictedparts(4, 3)))
# [1] 14

num.partitions(restrictedparts(8, 4))
# [1] 2795
ncol(setparts(restrictedparts(8, 4)))
# [1] 2795

Now let's look at your large case:

num.partitions(restrictedparts(15, 4))
# [1] 44747435

That is indeed quite a lot of partitions... Regardless of how well or not setparts is written, the output cannot fit in a single array:

sets <- matrix(1, 15, 44747435)
# Error in matrix(1, 15, 44747435) : 
#  cannot allocate vector of length 671211525

So yes, you'd have to write your own algorithm and store to a list of matrices, or if it is too much for your memory, write to a file if that's really what you want to do. Otherwise, given the rather large number of permutations and what it is you want to do with them, go back to the drawing board...

Creating a list with column-wise partitions of a data.frame

It is actually easier to define a function with the splitting sequence. The key functions here are repand split.default i.e.

f2 <- function(df, n, split){
  i1 <- rep(seq(n), split)
  res_list <- split.default(df[-1], i1)
  return(lapply(res_list, function(i)cbind.data.frame(ID = df$id, i)))
}

f2(df, 3, c(1, 1, 2))
$`1`
   ID          x1
1   1  1.54960977
2   2 -1.59144017
3   3  0.02853548
4   4 -0.14231391
5   5  1.26989801
6   6  0.87495876
7   7  0.27373774
8   8 -0.75600983
9   9  0.32216493
10 10 -1.05113771

$`2`
   ID         x2
1   1  0.8529416
2   2  0.4555094
3   3 -0.3620756
4   4  1.4779813
5   5 -1.6484066
6   6 -0.5697431
7   7 -0.2139384
8   8  0.1619074
9   9 -0.5390306
10 10 -0.2228809

$`3`
   ID         x3           x4
1   1 -0.2579865  1.185526074
2   2 -0.0519554 -0.388179976
3   3  2.5350092 -0.675504829
4   4 -1.7051955  0.073448252
5   5  0.6207733 -0.637220508
6   6  0.3015831 -1.324024114
7   7 -0.5647717  0.969025962
8   8  0.1404714 -1.575383604
9   9  1.3049560 -1.846413101
10 10 -0.6716643  0.008675125

f2(df, 3, c(1, 2, 1))
$`1`
   ID          x1
1   1  1.54960977
2   2 -1.59144017
3   3  0.02853548
4   4 -0.14231391
5   5  1.26989801
6   6  0.87495876
7   7  0.27373774
8   8 -0.75600983
9   9  0.32216493
10 10 -1.05113771

$`2`
   ID         x2         x3
1   1  0.8529416 -0.2579865
2   2  0.4555094 -0.0519554
3   3 -0.3620756  2.5350092
4   4  1.4779813 -1.7051955
5   5 -1.6484066  0.6207733
6   6 -0.5697431  0.3015831
7   7 -0.2139384 -0.5647717
8   8  0.1619074  0.1404714
9   9 -0.5390306  1.3049560
10 10 -0.2228809 -0.6716643

$`3`
   ID           x4
1   1  1.185526074
2   2 -0.388179976
3   3 -0.675504829
4   4  0.073448252
5   5 -0.637220508
6   6 -1.324024114
7   7  0.969025962
8   8 -1.575383604
9   9 -1.846413101
10 10  0.008675125

How to split a list into n groups in all possible combinations of group length and elements within group in R?

If you want an easy implementation for the similar objective, you can try listParts from package partitions, e.g.,

> x <- 4

> partitions::listParts(x)
[[1]]
[1] (1,2,3,4)

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

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

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

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

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

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

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

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

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

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

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

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

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

[[15]]
[1] (1)(2)(3)(4)

where x is the number of elements in the set, and all partitions denotes the indices of elements.

If you want to choose the number of partitions, below is a user function that may help

f <- function(x, n) {
  res <- listParts(x)
  subset(res, lengths(res) == n)
}

such that

> f(x, 2)
[[1]]
[1] (1,2,4)(3)

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

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

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

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

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

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

> f(x, 3)
[[1]]
[1] (1,4)(2)(3)

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

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

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

[[5]]x
[1] (2,3)(1)(4)

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

Update
Given x <- LETTERS[1:4], we can run

res <- rapply(listParts(length(x)), function(v) x[v], how = "replace")

such that

> res
[[1]]
[1] (A,B,C,D)

[[2]]
[1] (A,B,D)(C)

[[3]]
[1] (A,B,C)(D)

[[4]]
[1] (A,C,D)(B)

[[5]]
[1] (B,C,D)(A)

[[6]]
[1] (A,D)(B,C)

[[7]]
[1] (A,B)(C,D)

[[8]]
[1] (A,C)(B,D)

[[9]]
[1] (A,D)(B)(C)

[[10]]
[1] (A,B)(C)(D)

[[11]]
[1] (A,C)(B)(D)

[[12]]
[1] (B,D)(A)(C)

[[13]]
[1] (B,C)(A)(D)

[[14]]
[1] (C,D)(A)(B)

[[15]]
[1] (A)(B)(C)(D)

Get all sets of numerically-contiguous subsequences of a vector?

You can try the code below using split + findInterval + combn

v <- seq_along(x)
Map(
  split,
  list(x),
  unique(
    lapply(
      unlist(
        sapply(
          seq_along(v),
          function(k) combn(v, k, simplify = FALSE)
        ),
        recursive = FALSE
      ),
      function(p) {
        cumsum(duplicated(findInterval(v, p)))
      }
    )
  )
)

Some example results

For x <- 1:3, we obtain

[[1]]
[[1]]$`0`
[1] 1

[[1]]$`1`
[1] 2

[[1]]$`2`
[1] 3

[[2]]
[[2]]$`0`
[1] 1 2

[[2]]$`1`
[1] 3

[[3]]
[[3]]$`0`
[1] 1

[[3]]$`1`
[1] 2 3

[[4]]
[[4]]$`0`
[1] 1 2 3

For x <- 1:4, we obtain

[[1]]
[[1]]$`0`
[1] 1

[[1]]$`1`
[1] 2

[[1]]$`2`
[1] 3

[[1]]$`3`
[1] 4

[[2]]
[[2]]$`0`
[1] 1 2

[[2]]$`1`
[1] 3

[[2]]$`2`
[1] 4

[[3]]
[[3]]$`0`
[1] 1

[[3]]$`1`
[1] 2 3

[[3]]$`2`
[1] 4

[[4]]
[[4]]$`0`
[1] 1

[[4]]$`1`
[1] 2

[[4]]$`2`
[1] 3 4

[[5]]
[[5]]$`0`
[1] 1 2 3

[[5]]$`1`
[1] 4

[[6]]
[[6]]$`0`
[1] 1 2

[[6]]$`1`
[1] 3 4

[[7]]
[[7]]$`0`
[1] 1

[[7]]$`1`
[1] 2 3 4

[[8]]
[[8]]$`0`
[1] 1 2 3 4

How to iterate over all possible partitions of a slice (non-empty subslices)?

Here's a way to do it recursively with minimal storage, and without needing to make copies, by passing a closure to handle each partition as it is generated:

fn iterate_all_subdivisions<'a, T, F>(head: &mut Vec<&'a [T]>, rest: &'a [T], f: &mut F)
where
    F: FnMut(&[&[T]]),
{
    if rest.len() == 0 {
        f(head);
    } else {
        for i in 1..=rest.len() {
            let (next, tail) = rest.split_at(i);
            head.push(next);
            iterate_all_subdivisions(head, tail, f);
            head.pop();
        }
    }
}

fn main() {
    let v: Vec<i32> = vec![1, 2, 3];
    iterate_all_subdivisions(&mut Vec::new(), &v, &mut |x| println!("{:?}", x));
}

This will output:

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

If you do want to accumulate all the partitions into a Vec, you could do it like this:

fn main() {
    let v: Vec<i32> = vec![1, 2, 3];
    let mut results: Vec<Vec<Vec<i32>>> = Vec::new();
    iterate_all_subdivisions(&mut Vec::new(), &v, &mut |x| {
        results.push(x.iter().map(|y| y.to_vec()).collect());
    });
    println!("{:?}", results);
}

This will output

[[[1], [2], [3]], [[1], [2, 3]], [[1, 2], [3]], [[1, 2, 3]]]