Все N комбинаций всех подмножеств

Question

Для вектора элементов мне бы хотелось получить список всех возможных комбинаций подмножеств элементов. Например, учитывая (простейшее) последовательность 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)