所有子集的所有N个组合 [英] All N Combinations of All Subsets

问题描述

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

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}} }

当 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)
}

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

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).

推荐答案

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

This is what I would do, with, e.g., s=1:2:

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

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)))

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

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

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）将子集对表示为矩阵的行对：

2) Represent pairs of subsets as pairs of rows of the matrix:

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

此处，第十四行对应于子集，因此{1}& {1,2}。这假定对的顺序很重要（这在采用笛卡尔积时是隐含的）。要恢复子集，请使用 mypairosubsets = lapply（pairs [p，]，function（r）s [subsets [r，]]）其中 p 是您想要的货币对的行。

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.

将货币对扩展到 P（s）^ n 情况（其中 P（s）是 s 的幂集）例如

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.

复制 s 的元素可能对于之后所做的任何事情都是不必要的。但是，您可以通过使用 lapply（1：nrow（pairs），function（p）lapply（pairs [p，]，function（r）s [subsets [r，]]）从此处进行操作），其开头类似于...

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)

这篇关于所有子集的所有N个组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！