所有子集的所有 N 种组合

Question

给定一个元素向量，我想获得所有可能的 n-长度元素子集组合的列表。例如，给定（最简单的）序列 1:2，我想获得形式为

的列表对象

{ {{1},{1}}, {{1},{2}}, {{2},{2}}, {{1},{1,2}}, {{2},{1,2}}, {{1,2},{1,2}} }

当 n=2.

我能够使用以下方法生成所有非空子集的列表：

listOfAllSubsets <- function (s) {
  n <- length(s)
  unlist(lapply(1:n, function (n) {
    combn(s, n, simplify=FALSE)
  }), recursive=FALSE)
}

但是，我不确定从这里开始的最佳方式。本质上，我想要这个列表的笛卡尔积本身（n=2）。

有什么建议吗？最好使用非迭代解决方案（即没有 for 循环）。

Answer 1

这就是我要做的，例如 s=1:2:

1) 用每个元素的成员资格的 0/1 矩阵表示子集。

subsets = as.matrix(do.call(expand.grid,replicate(length(s),0:1,simplify=FALSE)))

这给出了

     Var1 Var2
[1,]    0    0
[2,]    1    0
[3,]    0    1
[4,]    1    1

这里，第一行是空子集；第二个，{1}；第三个，{2}；第四个，{1,2}。要获取子集本身，请使用 mysubset = s[subsets[row,]]，其中 row 是您想要的子集所在的行。

2) 将子集对表示为矩阵的行对：

pairs <- expand.grid(Row1=1:nrow(subsets),Row2=1:nrow(subsets))

这给出了

   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

这里第十四行对应subsets的第二行和第四行，所以{1} & {1,2}。这假设对的顺序很重要（这在采用笛卡尔积时是隐含的）。要恢复子集，请使用 mypairosubsets=lapply(pairs[p,],function(r) s[subsets[r,]])，其中 p 是您想要的对的行。

扩展到 P(s)^n 情况（其中 P(s) 是 s 的幂集）看起来像

setsosets = as.matrix(do.call(expand.grid,replicate(n,1:nrow(subsets),simplify=FALSE)))

在这里，每一行都有一个数字向量。每个数字对应 subsets 矩阵中的一行。

制作 s 的元素的副本可能对于您之后所做的任何事情都没有必要。但是，您可以从此处开始使用 lapply(1:nrow(pairs),function(p)lapply(pairs[p,],function(r) s[subsets[r,]]))，它的开头类似于...

[[1]]
[[1]]$Row1
integer(0)

[[1]]$Row2
integer(0)


[[2]]
[[2]]$Row1
[1] 1

[[2]]$Row2
integer(0)

Answer 2

从指数的笛卡尔积开始更容易。然后可以通过确保对索引元组进行排序来避免重复。

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

或者，对于 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

Answer 3

allSubsets<-function(n,# size of initial set
                     m,# number of subsets
                    includeEmpty=FALSE)# should the empty set be consiered a subset?

{

    # m can't exceed the number of possible subsets
    if(includeEmpty)
        stopifnot(m <= 2^n)
    else
        stopifnot(m <= 2^n-1)

    # get the subsets of the initial set (of size n)
    if(includeEmpty){
        ll <- split(t(combn(2^n,m)),seq(choose(2^n,m)))
    }else
        ll <- split(t(combn(2^n-1,m)),seq(choose(2^n-1,m)))

    # get the subets 
    subsets <- apply(do.call(expand.grid,rep(list(c(F,T)),n)),
                     1,which)
    # remove the empty subset if desired
    if(!includeEmpty)
        subsets <- subsets[-1]

    # covert the subsets to vector
    subsets <- lapply(subsets,as.vector)

    # return the list of subsets
    apply(t(mapply('[',list(subsets),ll)),1,function(x)x)

}

# returns a list where each element is a list of length 2 with 
# subsets of the initial set of length 4
x = allSubsets(4,2,F)

所有子集的所有 N 种组合

All N Combinations of All Subsets

r

combinatorics