Alle N-Kombinationen aller Teilmengen

Question

Gegeben ein Vektor von Elementen, würde ich gerne eine Liste aller möglichen n-Längen Kombinationen von Teilmengen von Elementen erhalten. Zum Beispiel, angesichts der (einfachste) -Sequenz 1:2, würde Ich mag eine Liste Ziel der Form

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

wenn n=2 zu erhalten.

ich in der Lage war, mit dem folgenden eine Liste aller nichtleeren Teilmengen zu generieren:

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

Allerdings bin ich der beste Weg, nicht sicher, von hier zu gehen. Im Wesentlichen möchte ich ein kartesisches Produkt dieser Liste mit sich selbst (für).

Irgendwelche Vorschläge? Eine nicht-iterative Lösung wäre vorzuziehen (d. H. Keine for Schleifen). Diese

Answer 1

ist das, was ich tun würde, mit, zum Beispiel s=1:2:

1) Stellen Sie Untergruppen mit einer 0/1 Matrix für jede Mitgliedschaft des Elements.

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

die

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

Hier wird die erste Zeile gibt, ist die leere Teilmenge; der zweite, {1}; der dritte, {2}; und der vierte, {1,2}. Um die Teilmenge selbst zu erhalten, verwenden Sie mysubset = s[subsets[row,]], wobei row die Zeile der gewünschten Teilmenge ist.

2) stellen Paare von Teilmengen als Paare von Reihen der Matrix:

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

die hier

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 

gibt, entspricht der vierzehnten Zeile in der zweiten und vierten Reihen von subsets, so {1} & {1,2}. Dies setzt voraus, dass die Reihenfolge des Paares wichtig ist (was bei der Verwendung des kartesischen Produkts impliziert ist). Verwenden Sie mypairosubsets=lapply(pairs[p,],function(r) s[subsets[r,]]) wo p die Zeile des Paares ist, das gewünscht wird, um die Teilmengen wiederherzustellen.

jenseits Paaren Expanding zum P(s)^n Fall (wo der Strom P(s) Satz von s ist) würde so aussehen

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

Hier wird jede Zeile ein Vektor von Zahlen aufweisen. Jede Nummer entspricht einer Zeile in der subsets Matrix.

---

Erstellen von Kopien der Elemente s ist wahrscheinlich nicht notwendig, was Sie danach tun. Allerdings könnte man es von hier aus tun, indem Sie lapply(1:nrow(pairs),function(p)lapply(pairs[p,],function(r) s[subsets[r,]])), die wie beginnt ...

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

[[1]]$Row2 
integer(0) 


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

[[2]]$Row2 
integer(0) 

Answer 2

Es ist einfacher, mit einem Kartesisches Produkt des Indizes zu starten. Dann kann die Duplizierung vermieden werden, indem sichergestellt wird, dass das Tupel der Indizes sortiert ist.

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 

Oder für 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)