Tutte le N Combinazioni di tutti i sottogruppi

Question

Dato un vettore di elementi, vorrei ottenere un elenco di tutte le possibili combinazioni di sottogruppi di elementi n. Ad esempio, data la (semplice) sequenza 1:2, desidero ottenere un oggetto lista di modulo

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

quando n=2.

sono stato in grado di generare un elenco di tutti i sottoinsiemi non vuoti utilizzando la seguente:

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

Tuttavia, non sono sicuro che il modo migliore di procedere da qui. Essenzialmente, voglio un prodotto cartesiano di questa lista con se stesso (per n=2).

Qualche suggerimento? Sarebbe preferibile una soluzione non iterativa (cioè, nessun loop for).

Answer 1

Questo è quello che avrei fatto, con, per esempio, s=1:2:

1) rappresentano parti con una matrice 0/1 per l'adesione di ciascun elemento.

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

che dà

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

Qui, la prima riga è il sottoinsieme vuoto; il secondo, {1}; il terzo, {2}; e il quarto, {1,2}. Per ottenere il sottoinsieme, utilizzare mysubset = s[subsets[row,]], dove row è la riga del sottoinsieme desiderato.

2) rappresentano coppie di sottoinsiemi come coppie di righe della matrice:

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

che dà

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 

Qui, la riga quattordicesimo corrisponde alla seconda e quarta fila subsets, così {1} & {1,2}. Ciò presuppone l'ordine della coppia (che è implicito nel prendere il prodotto cartesiano). Per ripristinare i sottoinsiemi, utilizzare mypairosubsets=lapply(pairs[p,],function(r) s[subsets[r,]]) dove p è la riga della coppia desiderata.

Espansione oltre coppie al caso P(s)^n (dove P(s) è l'insieme di potenza s) sarebbe simile

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

Qui, ogni riga avrà un vettore di numeri. Ogni numero corrisponde a una riga nella matrice subsets.

---

Esecuzione di copie degli elementi di s probabilmente non è necessaria per qualsiasi cosa stiate facendo dopo questo. Tuttavia, si potrebbe farlo da qui utilizzando lapply(1:nrow(pairs),function(p)lapply(pairs[p,],function(r) s[subsets[r,]])), che inizia così ...

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

[[1]]$Row2 
integer(0) 


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

[[2]]$Row2 
integer(0) 

Answer 2

E 'più facile iniziare con un prodotto cartesiano degli indici. Quindi la duplicazione può essere evitata assicurandosi che la tupla degli indici sia ordinata.

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 

Oppure, per 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)