How to get all unique permutations of a binary matrix with 6 columns and 12 rows?

Question

I am trying to produce all possible binary matrices order 12x6 containing elements only -1 and +1. There are 2^72 unique matrices (2^16), such that no two matrices contain the same element in the same coordinates.

I tried with the below code:

binary3.2 <- function(m, n) {
mn <- m*n
  perm <- RcppAlgos::permuteGeneral(c(-1,1), mn, TRUE)
  asplit(array(t(perm), c(m, n, 2^(m*n))), 3)
}

But it's giving me errors mentioning that m*n cannot be greater than 31. In my case, it is 72. Is there any other way to do this?

Even if you are storing the numbers as 32-bit integers, you would need at least 72 * 4 * 2^72 bytes of memory to do this calculation. This would require your computer to have over a _quadrillion_ gigabytes of memory. It's simply not a realistic thing to do. Why do you need _every_ permutation? You couldn't possibly use them all for anything. — Allan Cameron, Feb 03 '23 at 20:46

score 1 · Answer 1 · answered Feb 04 '23 at 15:46

First off, I am the author of RcppAlgos. There are a couple of ways around your current issue.

Before we start attacking your main issue, let’s start by simplifying your code a bit.

Using `FUN`

Instead of generating all permutations then calling asplit, we can make use of the FUN parameter to convert our vector to a matrix on the fly just as we can with combn:

library(RcppAlgos)
m <- 3L
n <- 2L

perms <- permuteGeneral(c(1L, -1L), m * n, TRUE, FUN = \(x) {
    matrix(x, m, n)
})

perms[1:2]
#> [[1]]
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1    1
#> [3,]    1    1
#> 
#> [[2]]
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1    1
#> [3,]    1   -1

perms[63:64]
#> [[1]]
#>      [,1] [,2]
#> [1,]   -1   -1
#> [2,]   -1   -1
#> [3,]   -1    1
#> 
#> [[2]]
#>      [,1] [,2]
#> [1,]   -1   -1
#> [2,]   -1   -1
#> [3,]   -1   -1

Attacking the Memory Problem

Using `lower` and `upper`

We can make use of the lower and upper parameters so that we can generate permutations in chunks:

## Generate the first 2 results
permuteGeneral(c(1L, -1L), m * n, TRUE, FUN = \(x) {
    matrix(x, m, n)
}, upper = 2)
#> [[1]]
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1    1
#> [3,]    1    1
#> 
#> [[2]]
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1    1
#> [3,]    1   -1

## Get the next 2 results
permuteGeneral(c(1L, -1L), m * n, TRUE, FUN = \(x) {
    matrix(x, m, n)
}, lower = 3, upper = 4)
#> [[1]]
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1   -1
#> [3,]    1    1
#> 
#> [[2]]
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1   -1
#> [3,]    1   -1

This gets the job done, however it is somewhat cumbersome.

Is there is a more elegant solution?

A Better Way

RcppAlgos offers combinatorial iterators so that one can generate n results at a time, thus keeping memory low.

Using iterators

iter <- permuteIter(c(1L, -1L), m * n, TRUE, FUN = \(x) {
    matrix(x, m, n)
})

## See the first result
iter@nextIter()
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1    1
#> [3,]    1    1

## Get the next 2 results (Note we are using nextNIter instead of nextIter)
iter@nextNIter(2)
#> [[1]]
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1    1
#> [3,]    1   -1
#> 
#> [[2]]
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1   -1
#> [3,]    1    1

The really nice thing about these iterators is that they are bidirectional and they also offer random access:

## See the previous result
iter@prevIter()
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1    1
#> [3,]    1   -1

## Get a quick summary
iter@summary()
#> $description
#> [1] "Permutations with repetition of 2 choose 6"
#> 
#> $currentIndex
#> [1] 2
#> 
#> $totalResults
#> [1] 64
#> 
#> $totalRemaining
#> [1] 62

## Go to the middle
middle <- permuteCount(2, m * n, TRUE) %/% 2L
middle
#> [1] 32
iter[[middle]]
#>      [,1] [,2]
#> [1,]    1   -1
#> [2,]   -1   -1
#> [3,]   -1   -1

## See the last result
iter@back()
#>      [,1] [,2]
#> [1,]   -1   -1
#> [2,]   -1   -1
#> [3,]   -1   -1

## Go back to the front
iter@front()
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    1    1
#> [3,]    1    1

And as for the question at hand, memory will be no problem!

m_big <- 12L
n_big <- 6L

iter_big <- permuteIter(c(1L, -1L), m_big * n_big, TRUE, FUN = \(x) {
    matrix(x, m_big, n_big)
})

iter_big@nextIter()
#>       [,1] [,2] [,3] [,4] [,5] [,6]
#>  [1,]    1    1    1    1    1    1
#>  [2,]    1    1    1    1    1    1
#>  [3,]    1    1    1    1    1    1
#>  [4,]    1    1    1    1    1    1
#>  [5,]    1    1    1    1    1    1
#>  [6,]    1    1    1    1    1    1
#>  [7,]    1    1    1    1    1    1
#>  [8,]    1    1    1    1    1    1
#>  [9,]    1    1    1    1    1    1
#> [10,]    1    1    1    1    1    1
#> [11,]    1    1    1    1    1    1
#> [12,]    1    1    1    1    1    1

iter_big@summary()
#> $description
#> [1] "Permutations with repetition of 2 choose 72"
#> 
#> $currentIndex
#> Big Integer ('bigz') :
#> [1] 1
#> 
#> $totalResults
#> Big Integer ('bigz') :
#> [1] 4722366482869645213696
#> 
#> $totalRemaining
#> Big Integer ('bigz') :
#> [1] 4722366482869645213695

iter_big@back()
#>       [,1] [,2] [,3] [,4] [,5] [,6]
#>  [1,]   -1   -1   -1   -1   -1   -1
#>  [2,]   -1   -1   -1   -1   -1   -1
#>  [3,]   -1   -1   -1   -1   -1   -1
#>  [4,]   -1   -1   -1   -1   -1   -1
#>  [5,]   -1   -1   -1   -1   -1   -1
#>  [6,]   -1   -1   -1   -1   -1   -1
#>  [7,]   -1   -1   -1   -1   -1   -1
#>  [8,]   -1   -1   -1   -1   -1   -1
#>  [9,]   -1   -1   -1   -1   -1   -1
#> [10,]   -1   -1   -1   -1   -1   -1
#> [11,]   -1   -1   -1   -1   -1   -1
#> [12,]   -1   -1   -1   -1   -1   -1

iter_big[["100"]]
#>       [,1] [,2] [,3] [,4] [,5] [,6]
#>  [1,]    1    1    1    1    1    1
#>  [2,]    1    1    1    1    1    1
#>  [3,]    1    1    1    1    1    1
#>  [4,]    1    1    1    1    1    1
#>  [5,]    1    1    1    1    1    1
#>  [6,]    1    1    1    1    1   -1
#>  [7,]    1    1    1    1    1   -1
#>  [8,]    1    1    1    1    1    1
#>  [9,]    1    1    1    1    1    1
#> [10,]    1    1    1    1    1    1
#> [11,]    1    1    1    1    1   -1
#> [12,]    1    1    1    1    1   -1

iter_big@prevNIter(2)
#> [[1]]
#>       [,1] [,2] [,3] [,4] [,5] [,6]
#>  [1,]    1    1    1    1    1    1
#>  [2,]    1    1    1    1    1    1
#>  [3,]    1    1    1    1    1    1
#>  [4,]    1    1    1    1    1    1
#>  [5,]    1    1    1    1    1    1
#>  [6,]    1    1    1    1    1   -1
#>  [7,]    1    1    1    1    1   -1
#>  [8,]    1    1    1    1    1    1
#>  [9,]    1    1    1    1    1    1
#> [10,]    1    1    1    1    1    1
#> [11,]    1    1    1    1    1   -1
#> [12,]    1    1    1    1    1    1
#> 
#> [[2]]
#>       [,1] [,2] [,3] [,4] [,5] [,6]
#>  [1,]    1    1    1    1    1    1
#>  [2,]    1    1    1    1    1    1
#>  [3,]    1    1    1    1    1    1
#>  [4,]    1    1    1    1    1    1
#>  [5,]    1    1    1    1    1    1
#>  [6,]    1    1    1    1    1   -1
#>  [7,]    1    1    1    1    1   -1
#>  [8,]    1    1    1    1    1    1
#>  [9,]    1    1    1    1    1    1
#> [10,]    1    1    1    1    1    1
#> [11,]    1    1    1    1    1    1
#> [12,]    1    1    1    1    1   -1

How to get all unique permutations of a binary matrix with 6 columns and 12 rows?

1 Answers1

Using FUN

Attacking the Memory Problem

Using lower and upper

A Better Way

Using iterators

Using `FUN`

Using `lower` and `upper`