Tất cả N kết hợp của tất cả các tập hợp con

Question

Cho một vectơ các phần tử, tôi muốn có được một danh sách tất cả các kết hợp có thể có của n-chiều dài của tập con của các phần tử. Ví dụ, đưa ra (đơn giản nhất) chuỗi 1:2, tôi muốn để có được một đối tượng danh sách các hình thức

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

khi n=2.

tôi đã có thể tạo ra một danh sách tất cả các tập con không rỗng bằng cách sử dụng sau đây:

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

Tuy nhiên, tôi không chắc chắn cách tốt nhất để tiến hành từ đây. Về cơ bản, tôi muốn có một sản phẩm Descartes của danh sách này với chính nó (cho n=2).

Mọi đề xuất? Một giải pháp không lặp lại sẽ thích hợp hơn (tức là, không có các vòng for).

Answer 1

Đây là những gì tôi sẽ làm gì, với, ví dụ, s=1:2:

1) Đại diện các tập con với một ma trận 0/1 cho các thành viên của mỗi phần tử.

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

mang đến cho

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

Ở đây, dòng đầu tiên là tập hợp con trống rỗng; thứ hai, {1}; thứ ba, {2}; và thứ tư, {1,2}. Để có được tập hợp con, sử dụng mysubset = s[subsets[row,]], trong đó row là hàng của tập hợp con bạn muốn.

2) Đại diện cho cặp tập con như cặp hàng của ma trận:

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

mang đến cho

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 

Ở đây, hàng XIV tương ứng với các hàng thứ hai và thứ tư của subsets, vì vậy {1} & {1,2}. Điều này giả định thứ tự của cặp quan trọng (đó là tiềm ẩn trong việc lấy sản phẩm Descartes). Để khôi phục các tập con, sử dụng mypairosubsets=lapply(pairs[p,],function(r) s[subsets[r,]]) trong đó p là hàng của cặp bạn muốn.

Mở rộng ngoài cặp với P(s)^n trường hợp (trong đó P(s) là tập hợp sức mạnh của s) sẽ trông như thế

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

Ở đây, mỗi hàng sẽ có một vector của các con số. Mỗi số tương ứng với một hàng trong ma trận subsets.

---

Có thể không cần thiết sao chép các thành phần của s cho bất kỳ điều gì bạn làm sau này. Tuy nhiên, bạn có thể làm điều đó từ đây bằng cách sử dụng lapply(1:nrow(pairs),function(p)lapply(pairs[p,],function(r) s[subsets[r,]])), mà bắt đầu như thế ...

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

[[1]]$Row2 
integer(0) 


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

[[2]]$Row2 
integer(0) 

Answer 2

Nó là dễ dàng hơn để bắt đầu với một sản phẩm Descartes của các chỉ số. Sau đó, có thể tránh trùng lặp bằng cách đảm bảo rằng các chỉ mục được sắp xếp.

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 

Hoặc, cho 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)