# Step-by-step comparison between Permutation vs Combination

I remember the first time I got to know the concept of Permutation and Combination was back in my secondary school time. It was a really confusing concept to wrap my head around.

Lately, when I started practicing programming, Permutation and Combination came up again. However, this time, not the concept that caused me problem, but the actual programming technique that gave me a hard time to understand how to to implement them. Therefore, I decided to write this to hopefully have a more structured way to see the difference and how to implement them properly.

# Quick recap

In this post, I’ll mainly focus on the programming aspect of permutation and combination, and therefore, I’m assuming their mathematical concepts are already familiar with the reader. (Wikipedia has pretty thorough write ups for their concepts in case you need a refresh: Permutation, Combination).

TL;DR, below is my quick definition whenever I heard of them:

For combination, it can be understood as a collection of subsets of a set (without ordering).

For permutation, it’s similar to combination, but with ordering.

Example 1

Given an array `arr = [0, 1, 2]`.

• 3-element combination of arr is `(0, 1, 2)`.
• However, 3-element permutation of arr is `(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)` (since ordering is taken into consideration).

For both Combination and Permutation, it can be seen that they both depend on 2 different factors: number of elements used for combination / permutation, and the size of the array.

Example 2

With the same arr used in Example 1, this time, for each permutation / combination, instead of taking 3 elements from a length 3 array, if we take 2 elements, the results will be as follow:

• 2-element combination of a size 3 array `arr` : `(0, 1), (0, 2), (1, 2)`
• 2-element permutation of a size 3 array `arr` : `(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)`

As we can see, Example 1 is a special case of the k-element combination / permutation of a size n arr, with k happened to be n. Example 2 is a more general case in which k is just a value between 0 and n.

In this post, we will try to solve the problem in 2 different ways (2 problems):

• Find all possible combinations / permutations of an array.
• Find k-element combinations / permutations of an array.

# Problem type 1: find all possible combinations / permutations of an array

• Combinations of a size-n array

Since combination is just a collection of all subsets of an array, and for each subset, an element in the array will either appear or missing from the current subset. By utilizing that intuition, several approaches can be used to generate combinations. Below snippet is the idea of using backtracking for generating all combinations. Other approaches that can be thought of is Cascading or utilizing binary representations of value between 0 and `2^n` (stay tuned, there will be a separate post about different approaches for generating combinations).

Output of the above snippet is:

`[[], , [0, 1], [0, 2], , ]`
• Permutations of a size-n array

Unlike combination, generating all permutations of an array usually means generate all n-element permutation of a size-n array. Therefore, this section will focus on solving just this.

The idea is to swap values between elements. For every swap, a new permutation is created. Below snippet is just an example of how to achieve it using backtracking. Other approaches / solutions can be used as well (both recursive and iterative approaches are available. This will be covered in a separate post).

Output of the above snippet is:

`[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 1, 0], [2, 0, 1]]`

# Problem type 2: k-element combination / permutation of a size-n array

Unlike problem type 1, problem type 2 will just focus on a specific k-element combination / permutation of a size-n array.

• k-element combination of a size-n array

If we look at the implementation of combination solution in problem type 1, the solution is built up one element at a time (appending `current_combination` ). Therefore, k-element combination of a size-n array is just a state of the solution in the all combinations case. By utilizing that, the solution for this can be very similar to the solution in problem type 1, except some modification needs to be made (introducing `k_elements` parameter, and and early stopping logic in `line 15 — 17` of the below snippet).

Output of the above snippet is:

`[[0, 1], [0, 2], [1, 2]]`
• k-element permutation of a size-n array

Since permutation is combination with ordering taken into consideration, one solution could be to first generate k-element combination of a size-n array, and for each combination (a.k.a subset), generate all permutations of it. However, this approach is complicated since we have to implement both combination and permutation algorithms. Below snippet is a simple approach to generate all k-element permutations. The `k_elements` parameter is introduced to early stop the generation of the permutations (line 6–8).

Output of the above snippet is:

`[[1, 2], [1, 3], [2, 1], [2, 3], [3, 2], [3, 1]]`

Combinatorial problems are such an interesting set of problems which include some mathematical thinking as well as different programming techniques / algorithms for implementing solutions. This post is just an introduction about combination and permutation using recursive approach (backtracking). There are other interesting approaches (both recursive and iterative) that can be used. More detailed posts about this topic will be published later.

Stay tuned!
Happy coding.

Work hard, stay humble

Work hard, stay humble