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 <- 14
l <- 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 = 2
all_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 = 3
all_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 = 10
set.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 secs
length(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 Elements
arrange(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 important
arrange(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:

## Functions
library(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 cell
v = {v1,v2,v3};

% We unpack our cell into combvec
combvec(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} = ...

---

Related Topics