Combinations and permutations are two common operations applied to a collection of elements. There are also formulas to calculate the number of possible combinations or permutations, which sometimes can be leveraged to directly get answers which otherwise may require going through every possible case.
Combination
A combination selects certain number of items from a collection while the order of selection does not matter. For example, given a set with \(n\) elements, we select \(k\) elements from the set, where \(k\le n\). With a given \(k\), we are interested in learning the number of distinct combinations. Note that for calculating the number of combinations, we treat each element as unique. The result can be represented and calculated as below:
$$ \begin{aligned} & C(n,k) = C_k^n = {n \choose k} \\ & \\ = & {n! \over k!(n-k)!} = {n(n-1) \cdots (n-k+1) \over k(k-1) \cdots 1} \end{aligned} $$
Application
Given a collection of elements with distinct values, one typical application of combinations is to enumerate all subsets. This can be implemented in two ways. For example, we can generate each subset based on its size. That is, we first generate all possible subsets with a size of 1, then subsets with a size of 2, and so on until the collection itself (which is also a subset). Alternatively, to generate a subset, we traverse the collection, and for each element, we either select or ignore it for the subset.
What if the collection contains duplicates? To enumerate subsets from a collection that might contain duplicates, the strategy is to first sort the collection. Then for each element, we can ignore it if it’s duplicated with the previous element.
Another interesting scenario is to calculate possible unique paths between two points of a grid. While recursion and dynamic programming are more intuitive solutions, solving it through combinations is faster. For example, with a \(7\times 3\) grid where we are only allowed to move either down or right at any point in time, a path from the top-left corner to the bottom-right corner always involves 6 right steps and 2 down steps. To form a possible path, among the total 8 steps, we select a subset with a size of 6 to be right steps and leave the rest as down steps. The number of such paths is thus \(C(8, 6)\) (or \(C(8, 2)\) if we think of it as selecting a subset with a size of 2 to be down steps and leaving the rest as right steps).
Permutation
A permutation rearranges the elements of a collection into a certain different order. Permutations can also be used to form subsets from a collection. Different from combinations, orders do matter here. For example, given a set with \(n\) elements, we select \(k\) elements from the set, where \(k\le n\) and two selections with the same elements in different orders are considered two unique subsets. With a given \(k\), we are interested in learning the number of distinct permutations. Note that for calculating the number of permutations, we treat each element as unique. The result can be represented and calculated as below:
$$ \begin{aligned} & P(n,k) = P_k^n \\ & \\ = & {n! \over (n-k)!} = n(n-1) \cdots (n-k+1) \end{aligned} $$
Both permutations and combinations can be used to form subsets. Given a subset with a size of \(k\), the number of permutations over it is \(P(k,k)\) (i.e., \(k!\)). Therefore, the above permutation formula can also be deducted from the combination formula:
$$ \begin{aligned} P(n,k) & = C(n,k)\times P(k,k) \\ & \\ & = {n! \over k!(n-k)!} \times {k! \over (k-k)!} \\ & \\ & = {n! \over (n-k)!} \end{aligned} $$
Application
Given an array of elements with distinct values, one typical application is to enumerate all possible permutations. One idea is to enumerate possible elements for each position of the array. This can be implemented recursively. Specifically, for every element, we place it in the head of the array and then generate all possible permutations for the rest elements. We repeat this recursively until there is only one element left placing in the end of the array. Such process can be done in-place by swapping elements.
What if the array contains duplicates? To enumerate permutations from an array that might contain duplicates, we maintain a hash table to record the element values that have been enumerated for a particular position of the array. Different from combinations where a sorted collection facilitates the elimination of duplicates, the cost of sorting becomes higher for permutations that are done in-place. An in-place permutation relies on element swapping, while a swap of elements can break the sorted order. We thus have to apply sorting for each recursive step.
Another interesting scenario is to rearrange an array into the lexicographically next greater permutation. This can be done in-place with one pass. Specifically, we first identify the last descending sequence \(s\) in the end of the array. Suppose \(x\) is the element right before \(s\). For elements in \(s\) whose values are larger than that of \(x\), we get the one with the smallest value, say \(y\). We then swap \(x\) and \(y\). Note that now \(s\) is still a descending sequence. We reverse the sequence \(s\). The final array is then the result.