Trova tutti i modi possibili per dividere un elenco di elementi in un dato numero di gruppi della stessa dimensione

Question

Ho una lista di elementi e voglio un oggetto che mi dia tutti i modi possibili di suddividere questi elementi in un dato numero di gruppi della stessa dimensione

Per esempio Ecco la mia lista:

MyElements <- c(1,2,3,4) 

E voglio tutte le possibili combinazioni di essi spliting in 2 gruppi:

nb.groups <- 2 

La potenza risposta per esempio essere di questo tipo:

[[1]] 

[1] 1,2 

[2] 3,4 

[[2]] 

[1] 1,3 

[2] 2,4 

[[3]] 

[1] 2,3 

[2] 1,4 

Voglio evitare la ripetizione di quel tipo:

[[1]] 

[1] 1,2 

[2] 3,4 

[[2]] 

[1] 3,4 

[2] 1,2 

Grazie mille!

Grazie per la risposta. Penso che dovrei darti maggiori informazioni su quello che sto cercando di ottenere.

l'elenco (o vettore perché ovviamente MyElements era un vettore) è in realtà numeri di ID per gli individui. Voglio una lista di tutti i modi possibili per suddividere questi individui in un numero desiderato di gruppi che hanno tutti la stessa dimensione.

Se non sbaglio, l'unica soluzione che attualmente funziona per il momento è la cosiddetta soluzione brute-force-and-dirty di Juba. Ma come ha detto Juba, diventa rapidamente (troppo velocemente per i miei scopi!) Inutilizzabile.

Grazie ancora

Answer 1

Seguendo la logica ricorsiva consente di calcolare tutte le combinazioni, senza ripetizioni e senza la necessità di calcolare tutti loro prima. Funziona molto bene, a condizione che scegli (nx-1, ning-1) restituisca un intero. In caso contrario, calcolare le possibilità è un po 'ridicolo.

È un processo ricorsivo, quindi potrebbe richiedere molto tempo e causerà problemi di memoria quando i vettori superano un certo limite. Ma poi di nuovo, la divisione di un insieme di 14 elementi in 7 gruppi offre già 135135 possibilità uniche. Le cose sfuggono di mano molto velocemente in questo genere di cose.

La logica di pseudo-qualcosa (non sarebbe chiamarlo pseudocodice)

nb = number of groups 
ning = number of elements in every group 
if(nb == 2) 
    1. take first element, and add it to every possible 
     combination of ning-1 elements of x[-1] 
    2. make the difference for each group defined in step 1 and x 
     to get the related second group 
    3. combine the groups from step 2 with the related groups from step 1 

if(nb > 2) 
    1. take first element, and add it to every possible 
     combination of ning-1 elements of x[-1] 
    2. to define the other groups belonging to the first groups obtained like this, 
     apply the algorithm on the other elements of x, but for nb-1 groups 
    3. combine all possible other groups from step 2 
     with the related first groups from step 1 

Traducendo questo a R ci dà:

perm.groups <- function(x,n){ 
    nx <- length(x) 
    ning <- nx/n 

    group1 <- 
     rbind(
     matrix(rep(x[1],choose(nx-1,ning-1)),nrow=1), 
     combn(x[-1],ning-1) 
    ) 
    ng <- ncol(group1) 

    if(n > 2){ 
     out <- vector('list',ng) 

     for(i in seq_len(ng)){ 
     other <- perm.groups(setdiff(x,group1[,i]),n=n-1) 
     out[[i]] <- lapply(seq_along(other), 
         function(j) cbind(group1[,i],other[[j]]) 
        ) 
     } 
    out <- unlist(out,recursive=FALSE) 
    } else { 
     other <- lapply(seq_len(ng),function(i) 
        matrix(setdiff(x,group1[,i]),ncol=1) 
       ) 
     out <- lapply(seq_len(ng), 
        function(i) cbind(group1[,i],other[[i]]) 
      ) 
    } 
    out  
} 

Per vederlo funziona:

> perm.groups(1:6,3) 
[[1]] 
    [,1] [,2] [,3] 
[1,] 1 3 5 
[2,] 2 4 6 

[[2]] 
    [,1] [,2] [,3] 
[1,] 1 3 4 
[2,] 2 5 6 

[[3]] 
    [,1] [,2] [,3] 
[1,] 1 3 4 
[2,] 2 6 5 

[[4]] 
    [,1] [,2] [,3] 
[1,] 1 2 5 
[2,] 3 4 6 

[[5]] 
    [,1] [,2] [,3] 
[1,] 1 2 4 
[2,] 3 5 6 

[[6]] 
    [,1] [,2] [,3] 
[1,] 1 2 4 
[2,] 3 6 5 

[[7]] 
    [,1] [,2] [,3] 
[1,] 1 2 5 
[2,] 4 3 6 

[[8]] 
    [,1] [,2] [,3] 
[1,] 1 2 3 
[2,] 4 5 6 

[[9]] 
    [,1] [,2] [,3] 
[1,] 1 2 3 
[2,] 4 6 5 

[[10]] 
    [,1] [,2] [,3] 
[1,] 1 2 4 
[2,] 5 3 6 

[[11]] 
    [,1] [,2] [,3] 
[1,] 1 2 3 
[2,] 5 4 6 

[[12]] 
    [,1] [,2] [,3] 
[1,] 1 2 3 
[2,] 5 6 4 

[[13]] 
    [,1] [,2] [,3] 
[1,] 1 2 4 
[2,] 6 3 5 

[[14]] 
    [,1] [,2] [,3] 
[1,] 1 2 3 
[2,] 6 4 5 

[[15]] 
    [,1] [,2] [,3] 
[1,] 1 2 3 
[2,] 6 5 4 

Answer 2

Ecco un brute-force-and-dirty soluzione, che può funzionare per diverso numero di gruppi, ma si dovrebbe davvero provarlo prima dell'uso. Inoltre, in quanto utilizza permn, sarà inutilizzabile molto veloce a seconda delle dimensioni del vostro vettore:

library(combinat) 
split.groups <- function(x, nb.groups) { 
    length.groups <- length(x)/nb.groups 
    perm <- permn(x) 
    perm <- lapply(perm, function(v) { 
    m <- as.data.frame(matrix(v, length.groups, nb.groups)) 
    m <- apply(m,2,sort) 
    m <- t(m) 
    m <- m[order(m[,1]),] 
    rownames(m) <- NULL 
    m}) 
    unique(perm) 
} 

che dà, per esempio:

R> split.groups(1:4, 2) 
[[1]] 
    [,1] [,2] 
[1,] 1 2 
[2,] 3 4 

[[2]] 
    [,1] [,2] 
[1,] 1 4 
[2,] 2 3 

[[3]] 
    [,1] [,2] 
[1,] 1 3 
[2,] 2 4 

Oppure:

R> split.groups(1:6, 3) 
[[1]] 
    [,1] [,2] 
[1,] 1 2 
[2,] 3 4 
[3,] 5 6 

[[2]] 
    [,1] [,2] 
[1,] 1 2 
[2,] 3 6 
[3,] 4 5 

[[3]] 
    [,1] [,2] 
[1,] 1 6 
[2,] 2 3 
[3,] 4 5 

[[4]] 
    [,1] [,2] 
[1,] 1 2 
[2,] 3 5 
[3,] 4 6 

[[5]] 
    [,1] [,2] 
[1,] 1 6 
[2,] 2 5 
[3,] 3 4 

[[6]] 
    [,1] [,2] 
[1,] 1 5 
[2,] 2 6 
[3,] 3 4 

[[7]] 
    [,1] [,2] 
[1,] 1 5 
[2,] 2 3 
[3,] 4 6 

[[8]] 
    [,1] [,2] 
[1,] 1 5 
[2,] 2 4 
[3,] 3 6 

[[9]] 
    [,1] [,2] 
[1,] 1 6 
[2,] 2 4 
[3,] 3 5 

[[10]] 
    [,1] [,2] 
[1,] 1 4 
[2,] 2 3 
[3,] 5 6 

[[11]] 
    [,1] [,2] 
[1,] 1 4 
[2,] 2 6 
[3,] 3 5 

[[12]] 
    [,1] [,2] 
[1,] 1 4 
[2,] 2 5 
[3,] 3 6 

[[13]] 
    [,1] [,2] 
[1,] 1 3 
[2,] 2 5 
[3,] 4 6 

[[14]] 
    [,1] [,2] 
[1,] 1 3 
[2,] 2 6 
[3,] 4 5 

[[15]] 
    [,1] [,2] 
[1,] 1 3 
[2,] 2 4 
[3,] 5 6 

Answer 3

qui una soluzione basata sulla costruzione della colonna splitter.

x <- 1:4 
a <- as.data.frame(t(combn(x,length(x)/2)) 
a$sum <- abs(rowSums(a)-mean(rowSums(a))) 
lapply(split(a,a$sum),function(x) if(dim(x)[1]>2) 
             split(x,1:(dim(x)[1]/2)) 
            else 
             x) 



$`0` 
    V1 V2 sum 
3 1 4 0 
4 2 3 0 

$`1` 
    V1 V2 sum 
2 1 3 1 
5 2 4 1 

$`2` 
    V1 V2 sum 
1 1 2 2 
6 3 4 2