Permutations and Combinations

A mathematical permutation is a rearrangement of items. A mathematical combination is a subset of items. Together, combinations and permutations are sometimes called combinatorics. The R language has very limited built-in support for permutations and combinations, but it is possible to write your own program-defined functions. Figure 21 gives you an idea of where this chapter is headed.

Figure 21: Permutations and Combinations Demo

In section 4.1, we’ll look at how to create a permutation library using only a list object and related functions such as perm_init() and perm_display(). In section 4.2, we will examine how to generate a specified permutation element directly (rather than by iterating) by writing a perm_elem() function that uses a clever idea called the factoradic of a number.

In section 4.3, you’ll learn how to create a combination library using only a list object and related functions such as comb_init() and comb_display(). In section 4.4, we’ll see how to generate a specified combination element directly (rather than by iterating) by writing a comb_elem() function that uses a clever idea called the combinadic of a number.

4.1 Permutations

Although permutations are used in many areas of statistics and machine learning, R has very limited built-in support for permutations. You can write program-defined functions to create, display, and manipulate permutations.

Code Listing 11: Permutations

A mathematical permutation of order n is one possible arrangement of the numbers 1 through n. For example, one of the permutations of order n = 6 is (3, 1, 6, 5, 4, 2). When listed in lexicographical order, all 6 permutations of order n = 3 are:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

There are several ways to design a custom library for permutations. The demo program defines a permutation as a vector of integers with three related functions: perm_init(), perm_display(), and perm_succ(). You should also consider using alternative, more sophisticated designs such as list encapsulation or an S3, S4, or RC class.

The perm_init() function is defined as:

perm_init = function(n) {
  data = c(1:n)
  return(data)
}

The demo program calls perm_init() this way:

n <- 4
p <- perm_init(n)

The perm_display() function prints a permutation vector with leading and trailing # characters and with values separated by blank spaces:

perm_display = function(perm) {
  n <- length(perm)
  cat(“# “ )
  for (i in 1:n) {
    cat(perm[i], “ “, sep=““)
  }
  cat(“# \n”)
}

Notice that the order of a permutation can be determined by the length of the underlying vector.

When working with permutations, you will often want to generate all the permutations or the successor to a given permutation. The demo program defines a perm_succ() function to do this. The function can be called this way in order to generate all permutations for an order n:

p <- perm_init(n)
while (is.null(p) == FALSE) {
  perm_display(p)
  p <- perm_succ(p)
}

The stopping condition assumes that perm_succ() has been defined so that the successor to the last permutation element is NULL. Notice that you must use the built-in is.null() function rather than the == operator to check if an object is NULL.

Before iterating through all permutations of order n, you should consider determining how many permutation elements there are by using the built-in factorial() function. For example:

numPerms <- factorial(n)
cat(“Total number of permutations is”, numPerms, “\n”)

In most cases, it’s not practical to iterate through all permutations when n is larger than about 9 because 9! = 362,880, but 10! = 3,628,800 and 15! = 1,307,674,368,000.

The integer values in a permutation are often used to map to vector or list indices. For example, you could write a function that applies a permutation to a list this way:

perm_applyTo = function(perm, lst) {
  result <- list()
  n <- length(lst)
  for (i in 1:n) {
    result[i] <- lst[[perm[i]]]
  }
  return(result)
}

In summary, permutations are rearrangements of the numbers 1 through n. Essentially, the only built-in support for permutations in R are the sample() and factorial() functions. It’s relatively easy to implement your own permutation library in which a permutation is defined as a vector of integers plus related functions in order to initialize, display, and return a successor.

Resources

For information about factorial() and other specialized math functions, see:
https://stat.ethz.ch/R-manual/R-devel/library/base/html/Special.html.

For information about the sample() function, see:
https://stat.ethz.ch/R-manual/R-devel/library/base/html/sample.html.

4.2 Permutation element

A useful function when working with permutations is one that returns the mth lexicographical element. For example, if n = 4, there are 4! = 24 total elements. A call to perm_element(1) would return (1, 2, 3, 4), and a call to perm_element(23) would return (4, 3, 1, 2).

Code Listing 12: Direct Generation of a Permutation Element

There are 12! = 479,001,600 permutation elements for order n = 12. The demo program computes element 9,999,999 in two different ways. A naive approach for generating the mth element of a permutation starts with the first element, then calls a successor function m-1 times. However, this approach is only feasible for relatively small values of m. The demo program requires about 98 seconds using this iterative approach:

n <- as.integer(12)
p <- perm_init(n)
m <- 9999999
for (j in 1:(m-1)) {
  p = perm_succ(p)
}
perm_display(p)

We can also calculate the mth element of a permutation set directly by using the factoradic of a number. The factoradic of a number is a representation based on factorials. For example, in ordinary base 10 representation, the number 794 is (7 * 100) + (9 * 10) + (4 * 1).

Because 6! = 720, 5! = 120, 4! = 24, 3! = 6, 2! = 2, and 1! = 1, the number 794 can also be written as (103020) because 794 = (1 * 6!) + (0 * 5!) + (3 * 4!) + (0 * 3!) + (2 * 2!) + (0 * 1!). Although it’s not immediately obvious, you can calculate the mth permutation element by calculating the factoradic of m, which then maps to the element.

In function perm_element(), here is the code that computes the factoradic of m:

m <- m - 1
factoradic <- c(1:n)
for (j in 1:n) {
  factoradic[n-j+1] <- m %%j
  m <- m %/% j
}

for (i in 1:n) {
  factoradic[i] <- factoradic[i] + 1
}

First, m is converted from the usual R 1-based indexing to 0-based indexing. The %% operator is integer modulus. For example, 13 %% 5 = 3 because 5 goes into 13 two times with 3 left. The %/% operator is integer division. For example, 7 / 2 = 3.5, but 7 %/% 2 = 3.

After the factoradic of m has been calculated, it is used to generate the result permutation element this way:

result <- c(1:n)
result[n] <- 1
i <- n-1
while(i >= 1) {
  result[i] <- factoradic[i]
  for (j in (i+1):n) {
    if (result[j] >= result[i]) {
      result[j] <- result[j] + 1
    }
  }
  i <- i - 1
}

In summary, if you want to generate the mth element of a permutation set, you can iterate using a successor function if m is small. For large values of m, you can write a function that calculates the mth element directly by using the factoradic of m.

Resources

For additional information about the factoradic of a number, see:
https://en.wikipedia.org/wiki/Factorial_number_system.

4.3 Combinations

Although mathematical combinations are used in many areas of statistics and machine learning, R has very limited built-in support for combinations. You can write functions to create, display, and manipulate combinations.

Code Listing 13: Combinations

A mathematical combination of order (n, k) is one possible subset of k numbers from the numbers 1 through n, where order doesn’t matter. For example, one of the combinations of order (n = 7, k = 4) is (2, 3, 5, 7). The set (3, 2, 7, 5) is considered the same as (2, 3, 5, 7) because the order of the values doesn’t matter.

Listed in lexicographical order, here are all 10 combinations of order (n = 5, k = 3):

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Notice that if you see one combination element, you can infer k from the number of values in the element, but you can’t infer n.

A custom library for combinations can be designed several ways. The demo program defines a combination of order (n, k) as a vector of k integers with an additional cell that holds the value of n plus three related functions: comb_init(), comb_display(), and comb_succ(). You should also consider using list encapsulation or using an S3, S4, or RC class.

The comb_init() function is defined as:

comb_init = function(n, k) {
  data <- c(1:(k+1))
  data[k+1] <- n  # store n in dummy last cell
  return(data)
}

Function comb_init() can be called this way:

n <- as.integer(6)
k <- as.integer(4)
cmb <- comb_init(n, k)

These statements would create an integer vector named cmb that has five cells. The first four cells would hold (1, 2, 3, 4) and the fifth cell would hold 6, the value of n.

The comb_display() function is defined as:

comb_display = function(comb) {
  len <- length(comb)
  k <- len - 1
  n <- comb[len]

  cat(“^ “ )
  for (i in 1:k) {
    cat(comb[i], “ “, sep=““)
  }

  cat(“^ |”, n, “\n”)
}

The length() function directly yields the value of k (as length - 1) and indirectly yields the value of k (the value stored in cell [length]). The comb_display() function prints a combination element with leading and trailing ^ characters and with the value of n separated by a | character. You have many formatting alternatives available.

When working with combinations, you’ll often want to generate all combinations or the successor to a given combination. The demo program defines a comb_succ() function to do this. The function can be called this way in order to generate all combinations of order (n, k):

cmb <- comb_init(n, k)
while (is.null(cmb) == FALSE) {
  comb_display(cmb)
  cmb <- cmb_succ(cmb)
}

The stopping condition assumes that comb_succ() has been defined so that the successor to the last combination element is NULL. Before iterating through all combinations of order (n, k), you should consider determining how many elements are using the built-in choose() function. For example:

numCombs <- choose(n, k)

In summary, combinations are subsets of the numbers 1 through n. The choose() function and the sample() function are essentially the only built-in support for combinations in R. It’s relatively easy to implement your own combination library in which a combination is defined as a vector of integers plus related functions that initialize, display, and return a successor.

Resources

For information about choose() and other specialized math functions, see:
https://stat.ethz.ch/R-manual/R-devel/library/base/html/Special.html.

For information about the sample() function, see:
https://stat.ethz.ch/R-manual/R-devel/library/base/html/sample.html.

4.4 Combination element

When working with combinations, you’ll find that useful functions are those that return the mth lexicographical element. For example, if n = 10 and k = 3, there are choose(10, 3) = 120 total elements. A call to comb_element(1) would return (1, 2, 3), and a call to comb_element(120) would return (8, 9, 10).

Code Listing 14: Direct Generation of a Combination Element

For order n = 40 and k = 8, there are choose(40, 8) = 76,904,685 different combination elements. The demo program computes element 9,999,999 in two different ways. Starting with the first element, then calling a successor function m-1 times, is a naive approach for generating the mth element of a combination. However, this approach is only feasible for relatively small values of m. The demo program requires about 25 seconds using this iterative approach:

n <- as.integer(40)
k <- as.integer(8)
cmb <- cmb_init(n, k)
m <- 9999999
for (j in 1:(m-1)) {
  cmb = cmb_succ(cmb)
}
cmb_display(cmb)

You can also calculate the mth element of a combination set directly using what is called the combinadic of a number. The combinadic of a number is a representation based on the choose() function. For example, in ordinary base 10 representation, the number 27 is (2 * 10) + (7 * 1).

Suppose n = 7 and k = 4. The number 27 can also be written as (6, 5, 2, 1) because:

27 = choose(6, 4) + choose(5, 3) + choose(2, 2) + choose(1, 1) = 15 + 10 + 1 + 1

Although it’s not immediately obvious, you can calculate the mth combination element by calculating the combinadic of m, which then maps to the associated combination element.

In function comb_element(), the code that computes the combinadic of m begins with:

m <- m - 1
maxM <- choose(n, k) - 1
ans <- c(1:(k+1))
a <- n
b <- k
x <- maxM - m  # x is the dual of m

The input argument m is converted to 0-based indexing. Rather than computing the combinadic of m, the algorithm actually computes the combinadic of x, the 0-based dual of m. But the demo implementation of comb_elem() has a limitation—for large values of n and k, the built-in choose() function might overflow. A more robust implementation would use a BigInteger version of a choose function such as the one in the gmp add-on package.

Function comb_elem() computes a preliminary result into vector ans with this code:

for (i in 1:k) {
  v <- a - 1
  while (choose(v, b) > x) {
    v <- v - 1
  }
  ans[i] <- v
  x <- x - choose(v, b)
  a <- v
  b <- b - 1
}

When this code finishes execution, the desired combination element values are 0-based and stored as complements to n, which means they are converted to 1-based values and de-complemented. Also, the value of n is placed into the last cell of ans:

for (i in 1:k) {
  ans[i] <- n - ans[i]
}
ans[k+1] <- n

In summary, if you want to generate the mth element of a combination of order (n, k), and if m is small, you can iterate using a successor function. For large values of m, you can write a function that calculates the mth element directly by using the combinadic of m.

Resources

For additional information about the combinadic of a number, see:
https://en.wikipedia.org/wiki/Combinatorial_number_system.

For information about an add-on R package named combinat, see:
https://cran.r-project.org/web/packages/combinat/combinat.pdf.