﻿ Generate List of All Possible Combinations of Elements of Vector - ITCodar

# Generate List of All Possible Combinations of Elements of Vector

## Generate list of all possible combinations of elements of vector

You're looking for `expand.grid`.

``expand.grid(0:1, 0:1, 0:1)``

Or, for the long case:

``n <- 14l <- rep(list(0:1), n)expand.grid(l)``

## Generate all unique combinations from a vector with repeating elements

Use `combn()` with `lapply()` should do the trick.

``x <- c('red', 'blue', 'green', 'red', 'green', 'red')lapply(1:3, function(y) combn(x, y))# [[1]]     # [,1]  [,2]   [,3]    [,4]  [,5]    [,6] # [1,] "red" "blue" "green" "red" "green" "red"# [[2]]     # [,1]   [,2]    [,3]  [,4]    [,5]  [,6]    ...# [1,] "red"  "red"   "red" "red"   "red" "blue"  ...# [2,] "blue" "green" "red" "green" "red" "green" ...# [[3]]     # [,1]    [,2]   [,3]    [,4]   [,5]    [,6]    ...# [1,] "red"   "red"  "red"   "red"  "red"   "red"   ...# [2,] "blue"  "blue" "blue"  "blue" "green" "green" ...# [3,] "green" "red"  "green" "red"  "red"   "green" ...``

All unique combinations

``lapply(cc, function(y)  y[,!duplicated(apply(y, 2, paste, collapse="."))])[[1]][1] "red"   "blue"  "green"[[2]]     [,1]   [,2]    [,3]  [,4]    [,5]   [,6]    [,7]   [1,] "red"  "red"   "red" "blue"  "blue" "green" "green"[2,] "blue" "green" "red" "green" "red"  "red"   "green"[[3]]     [,1]    [,2]   [,3]    [,4]    [,5]    [,6]  [,7]    ...[1,] "red"   "red"  "red"   "red"   "red"   "red" "blue"  ...[2,] "blue"  "blue" "green" "green" "red"   "red" "green" ...[3,] "green" "red"  "red"   "green" "green" "red" "red"   ...``

Although strictly speaking those aren't all unique combinations, as some of them are permutations of each other.

Properly unique combinations

``lapply(cc, function(y)  y[,!duplicated(apply(y, 2, function(z) paste(sort(z), collapse=".")))])# [[1]]# [1] "red"   "blue"  "green"# [[2]]     # [,1]   [,2]    [,3]  [,4]    [,5]   # [1,] "red"  "red"   "red" "blue"  "green"# [2,] "blue" "green" "red" "green" "green"# [[3]]     # [,1]    [,2]   [,3]    [,4]    [,5]  [,6]   # [1,] "red"   "red"  "red"   "red"   "red" "blue" # [2,] "blue"  "blue" "green" "green" "red" "green"# [3,] "green" "red"  "red"   "green" "red" "green"``

## all possible combinations of a list of vectors

you could try

``lapply(2:3, function(k) { lapply(1:length(DF),function(x){ combn(DF[[x]],k,                           simplify = FALSE)})})``

## Generate all combinations of vector with consecutive occurrences is considered as single occurrence

Here's an approach using the very fast `arrangements` package for permutations. We calculate the permutations of integers corresponding to the unique elements of the input and then do some clever indexing to output the corresponding swaps. This is extremely fast on small examples and does pretty well on larger example - on my computer it took a little less than 7 seconds to generate the `10! = 3628800` swaps on input of size 30 with 10 unique elements. The results are conveniently returned in a `list`.

``library(arrangements)all_swaps = function(x) {  ux = unique(x)  xi = as.integer(factor(x))  perm = permutations(seq_along(ux))  apply(perm, MARGIN = 1, FUN = \(p) ux[p][xi], simplify = FALSE)}``

Test cases from the question:

``# n = 2all_swaps(c("a","a","a","b","b","b","a","a","b","b"))# [[1]]#  [1] "a" "a" "a" "b" "b" "b" "a" "a" "b" "b"# # [[2]]#  [1] "b" "b" "b" "a" "a" "a" "b" "b" "a" "a"## n = 3all_swaps(c("a","a","a","b","b","b","c","c","c"))# [[1]]# [1] "a" "a" "a" "b" "b" "b" "c" "c" "c"# # [[2]]# [1] "a" "a" "a" "c" "c" "c" "b" "b" "b"# # [[3]]# [1] "b" "b" "b" "a" "a" "a" "c" "c" "c"# # [[4]]# [1] "b" "b" "b" "c" "c" "c" "a" "a" "a"# # [[5]]# [1] "c" "c" "c" "a" "a" "a" "b" "b" "b"# # [[6]]# [1] "c" "c" "c" "b" "b" "b" "a" "a" "a"``

A shorter demo with 3 unique elements in a "complex" case where the elements are not all consecutive:

``all_swaps(c("a", "b", "b", "c", "b"))# [[1]]# [1] "a" "b" "b" "c" "b"# # [[2]]# [1] "a" "c" "c" "b" "c"# # [[3]]# [1] "b" "a" "a" "c" "a"# # [[4]]# [1] "b" "c" "c" "a" "c"# # [[5]]# [1] "c" "a" "a" "b" "a"# # [[6]]# [1] "c" "b" "b" "a" "b"``

A larger case:

``# n = 10set.seed(47)start_t = Sys.time()n10 = all_swaps(sample(letters[1:10], size = 30, replace = TRUE))end_t = Sys.time()end_t - start_t# Time difference of 6.711215 secslength(n10)# [1] 3628800``

#### Benchmarking

Benchmarking my answer with Maël's and ThomasIsCoding's, my method relying on the `arrangements` package is quick and memory efficient. ThomasIsCoding's answer can be improved by changing from `pracma::perms` to `arrangements::permutations`--the memory usage is especially improved--but my version still performs better. Maël's uses a lot of time and memory. I'll lead with results, code to reproduce is below.

``## 5 Unique Elementsarrange(b5, desc(`itr/sec`))# # A tibble: 4 × 13#   expression                  min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time#   <bch:expr>             <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm># 1 GregorThomas             2.31ms   12.6ms     77.5     5.77KB        0    40     0      516ms# 2 ThomasIsCodingArr(in5)    9.3ms   20.5ms     47.4    19.55KB        0    24     0      506ms# 3 ThomasIsCoding(in5)     12.57ms   22.7ms     41.2    45.41KB        0    22     0      534ms# 4 Mael                   963.64ms  963.6ms      1.04    1.24MB        0     1     0      964ms# # … with 4 more variables: result <list>, memory <list>, time <list>, gc <list>## 9 Unique Elements - memory allocation is importantarrange(b9, desc(`itr/sec`))# # A tibble: 2 × 13#   expression               min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result#   <bch:expr>          <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list># 1 GregorThomas            1.8s     1.8s     0.556    27.7MB    0         1     0       1.8s <NULL># 2 ThomasIsCoding(in9)     2.5s     2.5s     0.400   230.8MB    0.400     1     1       2.5s <NULL># # … with 3 more variables: memory <list>, time <list>, gc <list>``

Benchmarking code:

``## Functionslibrary(arrangements)library(pracma)ThomasIsCoding <- function(x) {  idx <- match(x, unique(x))  m <- asplit(matrix(unique(x)[perms(1:max(idx))], ncol = max(idx)), 1)  Map(`[`, m, list(idx))}ThomasIsCodingArr <- function(x) {  idx <- match(x, unique(x))  m <- asplit(matrix(unique(x)[permutations(1:max(idx))], ncol = max(idx)), 1)  Map(`[`, m, list(idx))}Mael <- function(vec){  uni <- unique(vec)  size <- length(uni)  pVec <- paste(uni, collapse = "")  grid <- expand.grid(rep(list(uni), size))  expanded <- grid[apply(grid, 1, function(x) length(unique(x))) == size,]  p <- unname(apply(expanded, 1, paste0, collapse = ""))    lapply(p, function(x) chartr(pVec, x, vec))}all_swaps = function(x) {  ux = unique(x)  xi = as.integer(factor(x))  perm = permutations(seq_along(ux))  apply(perm, MARGIN = 1, FUN = \(p) ux[p][xi], simplify = FALSE)}set.seed(47)in5 = c(sample(letters[1:5], 5), sample(letters[1:5], 5, replace = TRUE))b5 = bench::mark(  GregorThomas = all_swaps(in5),  Mael = Mael(in5),  ThomasIsCoding(in5),  ThomasIsCodingArr(in5),  check = FALSE)``

## All possible combinations of elements of three vectors in Python

You could use numpy.meshgrid() like so:

``np.array(np.meshgrid([4, 6], [2, 4], [1, 5])).T.reshape(-1,3)``

Which results in:

`` array([[4, 2, 1],       [4, 4, 1],       [6, 2, 1],       [6, 4, 1],       [4, 2, 5],       [4, 4, 5],       [6, 2, 5],       [6, 4, 5]])``

## How to get all possible combinations of array elements without duplicate

Judging from your desired result, you want all the combinations with 2 choices of `'A'`, `'B'`, `'C'`, and `''` (nothing). You can do it with `nchoosek` as follows

``result = nchoosek(' ABC', 2) % note space for empty``

Output

``result =  6×2 char array    ' A'    ' B'    ' C'    'AB'    'AC'    'BC'``

Then removing the spaces and converting the combinations to a cell array:

``result = strrep(cellstr(result), ' ', '')``

As Wolfie pointed out, this only works for single character input, for multi character inputs we can use string arrays instead of char arrays:

``result = nchoosek(["","A1","B2","C3"], 2);result = result(:,1) +  result(:,2) % string cat% result = cellstr(result); % optional if want cell output``
``result =   6×1 string array    "A1"    "B2"    "C3"    "A1B2"    "A1C3"    "B2C3"``

## R find all possible unique combinations

There are a few packages specifically built for this. The basic premise is that we need combinations with repetition of length `m` where `m` could be larger than the input vector. We start with the classic `gtools`:

``library(gtools)combinations(2, 3, letters[1:2], repeats.allowed = TRUE)    [,1] [,2] [,3][1,] "a"  "a"  "a" [2,] "a"  "a"  "b" [3,] "a"  "b"  "b" [4,] "b"  "b"  "b"``

And then there is `arrangements` which is a replacement for `iterpc` (the package linked by @Gregor in the comments above):

``library(arrangements)arrangements::combinations(2, 3, letters[1:2], replace = TRUE)     [,1] [,2] [,3][1,] "a"  "a"  "a" [2,] "a"  "a"  "b" [3,] "a"  "b"  "b" [4,] "b"  "b"  "b"``

And finally there is `RcppAlgos`, which I authored:

``library(RcppAlgos)comboGeneral(letters[1:2], 3, TRUE)     [,1] [,2] [,3][1,] "a"  "a"  "a" [2,] "a"  "a"  "b" [3,] "a"  "b"  "b" [4,] "b"  "b"  "b"``

`combn` is an awesome function that ships as one of the base packages with `R`, however one of its shortcomings is that it doesn't allow repetition (which is what is required here). I wrote a pretty comprehensive overview for problems exactly like this one that can be found here: A Walk Through a Slice of Combinatorics in R.

## generate all combinations of a variable number of vectors in MATLAB

You can unpack a cell with `mycell{:}`, if passed as an argument; each element of the cell will be interpreted as a new argument:

``v1 = [1,2,3];v2 = [2,3,4];v3 = [3,4,5];% We put everything in a cellv = {v1,v2,v3};% We unpack our cell into combveccombvec(v{:})``

Of course this example is pretty useless, but in a real case situation you can simply store your vectors directly in a cell `v{ii} = ...`