Given a vector of elements, I would like to obtain a list of all possible n
-length combinations of subsets of elements. For example, given the (simplest) sequence 1:2
, I would like to obtain a list object of the form
{ {{1},{1}}, {{1},{2}}, {{2},{2}}, {{1},{1,2}}, {{2},{1,2}}, {{1,2},{1,2}} }
when n=2
.
I was able to generate a list of all non-empty subsets using the following:
listOfAllSubsets <- function (s) {
n <- length(s)
unlist(lapply(1:n, function (n) {
combn(s, n, simplify=FALSE)
}), recursive=FALSE)
}
However, I'm not sure the best way to proceed from here. Essentially, I want a Cartesian product of this list with itself (for n=2
).
Any suggestions? A non-iterative solution would be preferable (i.e., no for
loops).
It is easier to start with a Cartesian product of the indices. Then duplication can be avoided by making sure the tuple of indices is sorted.
combosn <- function(items,n) {
i <- seq_along(items)
idx <-do.call(expand.grid,rep(list(i),n))
idx <- idx[!apply(idx,1,is.unsorted),]
apply(idx,1,function(x) items[x])
}
ss<-listOfAllSubsets(1:2)
str(combosn(ss,2))
List of 6 $ :List of 2 ..$ : int 1 ..$ : int 1 $ :List of 2 ..$ : int 1 ..$ : int 2 $ :List of 2 ..$ : int 2 ..$ : int 2 $ :List of 2 ..$ : int 1 ..$ : int [1:2] 1 2 $ :List of 2 ..$ : int 2 ..$ : int [1:2] 1 2 $ :List of 2 ..$ : int [1:2] 1 2 ..$ : int [1:2] 1 2
Or, for n=3
,
str(combosn(ss,3))
List of 10 $ :List of 3 ..$ : int 1 ..$ : int 1 ..$ : int 1 $ :List of 3 ..$ : int 1 ..$ : int 1 ..$ : int 2 $ :List of 3 ..$ : int 1 ..$ : int 2 ..$ : int 2 $ :List of 3 ..$ : int 2 ..$ : int 2 ..$ : int 2 $ :List of 3 ..$ : int 1 ..$ : int 1 ..$ : int [1:2] 1 2 $ :List of 3 ..$ : int 1 ..$ : int 2 ..$ : int [1:2] 1 2 $ :List of 3 ..$ : int 2 ..$ : int 2 ..$ : int [1:2] 1 2 $ :List of 3 ..$ : int 1 ..$ : int [1:2] 1 2 ..$ : int [1:2] 1 2 $ :List of 3 ..$ : int 2 ..$ : int [1:2] 1 2 ..$ : int [1:2] 1 2 $ :List of 3 ..$ : int [1:2] 1 2 ..$ : int [1:2] 1 2 ..$ : int [1:2] 1 2
This is what I would do, with, e.g., s=1:2
:
1) Represent subsets with a 0/1 matrix for each element's membership.
subsets = as.matrix(do.call(expand.grid,replicate(length(s),0:1,simplify=FALSE)))
which gives
Var1 Var2
[1,] 0 0
[2,] 1 0
[3,] 0 1
[4,] 1 1
Here, the first row is the empty subset; the second, {1}; the third, {2}; and the fourth, {1,2}. To get the subset itself, use mysubset = s[subsets[row,]]
, where row
is the row of the subset you want.
2) Represent pairs of subsets as pairs of rows of the matrix:
pairs <- expand.grid(Row1=1:nrow(subsets),Row2=1:nrow(subsets))
which gives
Row1 Row2
1 1 1
2 2 1
3 3 1
4 4 1
5 1 2
6 2 2
7 3 2
8 4 2
9 1 3
10 2 3
11 3 3
12 4 3
13 1 4
14 2 4
15 3 4
16 4 4
Here, the fourteenth row corresponds to the second and fourth rows of subsets
, so {1} & {1,2}. This assumes the order of the pair matters (which is implicit in taking the Cartesian product). To recover the subsets, use mypairosubsets=lapply(pairs[p,],function(r) s[subsets[r,]])
where p
is the row of the pair you want.
Expanding beyond pairs to the P(s)^n
case (where P(s)
is the power set of s
) would look like
setsosets = as.matrix(do.call(expand.grid,replicate(n,1:nrow(subsets),simplify=FALSE)))
Here, each row will have a vector of numbers. Each number corresponds to a row in the subsets
matrix.
Making copies of the elements of s
is probably not necessary for whatever you are doing after this. However, you could do it from here by using lapply(1:nrow(pairs),function(p)lapply(pairs[p,],function(r) s[subsets[r,]]))
, which starts like...
[[1]]
[[1]]$Row1
integer(0)
[[1]]$Row2
integer(0)
[[2]]
[[2]]$Row1
[1] 1
[[2]]$Row2
integer(0)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With