**Tags**

Algorithm, combinatorial algorithm, combinatorics, Data Structures, discrete mathematics, permutation and combination

https://leanpub.com/discretemathematicalalgorithmanddatastructures

The area of mathematics in which counting is the primarily concern, it is known as Combinatorics. Besides other subjects like statistical physics, it has many applications in Computer Science.

The counting capabilities and other abstractions of Combinatorics is implemented in different ways (algorithm) to obtain results. In like manner, it also studies certain properties of finite structures, like data structures in Computer science.

Primarily, any data structure is related to the abstractions of any finite sets. We can apply different types of permutations on finite sets and that study also plays an important role in the fields of Combinatorics.

We can assume that when different types of permutations are required for data structures, different types of algorithms can also be emerged out from there.

For a single problem where enumeration or counting is required, there can be different types of algorithms. We can approach the problems whatever way. Regardless of how we solve the problems, different algorithms emerge from it.

Furthermore, to know how Combinatorics is associated with data structures and algorithm, we need to know the basic operations that are acted upon on the data structures with the help of different types of algorithms.

Be that as it may, but we cannot ignore these facts.

We have already found that enumeration of a specified data structure is a part of Combinatorics. Arrangements of a certain data structure is also a part of it. We can restructure or rearrange any ‘string’ value and place the characters in different combinations.

We can check whether a data structure fulfils a certain criteria. If there are several possibilities, we can also check, with the help of algorithms, what is the best structure or solution.

We have just learned that study of Combinatorics deals with different types of permutations on finite sets or data structures.

Therefore, to understand the key abstractions of Combinatorics we need to understand what permutations and combinations are.

## Permutation and Combination

When we use the word ‘combination’, we forget whether ‘order’ is important or not. We also leave behind another key concept, ‘repetition’. When repetition is allowed, the number of combinations increase. When it is not allowed, the number of combination or, in other words, the number of rearrangement reduces.

Consider an example that will make it clear.

Take a word ‘forget’. If we go to any thesaurus and try to find what kind of word is it, we find several other words that are close to its meaning.

They are: overlook, drop, neglect, omit, leave out, etc. We can rearrange these group of words in many ways where order is not maintained. When we do not care what order the words are in, we say it a ‘combination’ of words.

However, when we apply the alphabetical order and rearrange the group of words again, then it comes out like this: drop, neglect, omit, overlook, leave out, etc. When order matters in a combination, it is called permutation.

Think about a combination lock. We can choose any three numbers from 0 to 10. If in our case, the combination works in this arrangement ‘562’, we can say that repetition is not allowed in this permutation. If it was like ‘223’, we could have said that repetition is allowed in this permutation.

Take a close look, we will find that any permutation where repetition is allowed, the number of possibilities is nothing but factorial of that number of things that are to be rearranged.

Consider any three things. How many ways we can rearrange them? Finding it is very easy.

```
3 * 2 * 1 = 6
```

There are 6 ways we can rearrange three elements. If there were 4 elements, the factorial of 4, that is, in 24 ways we could have rearranged those 4 things.

Enough theory; let us dive into our first code where we will find the best algorithm to solve the above problem.

```
package chapterten;
/**
* permutation is a combination of collections where order matters
* permutation could be with repetition or without
* here we see an example of
* permutations without repetition
* if there are 16 things, and if we choose 14
* then we cannot choose 14 again
* in that case, 15 things remain
* no repetitions and order matters
*/
/**
* Here is our problem:
* what order could 5 balls be in
* for 5 balls the possibility is factorial(5)
* if we take any otwo out of it
* the possibility is factorial(5 - 3)
* but the order of 2 out of 5 balls
* is factorial(5) / factorial(5 - 3)
*/
public class SimplePermutation {
static int permutationWithoutRepetition(int n){
int i = 1;
int k = 1;
while (i <= n){
k *= i;
i++;
}
//we get the factorial of the number we have passed as parameter
return k;
}
public static void main(String[] args) {
/**
* the formula of permutation without repetition
* is factorial(listOfNumbers)/factorial(listOfNumbers - restOfNumbers)
*/
int listOfNumbers = 5;
int restOfNumbers = 3;
System.out.println("The list of numbers are (5, 4, 3, 2, 1)");
System.out.println("Our first choice has 5 possibilities.");
System.out.println("The number of orders 5 numbers could be in: ");
System.out.println(permutationWithoutRepetition(5));
}
}
```

The output is quite expected. When 5 things are to be rearranged, there are 120 possibilities, which is actually the factorial of 5.

```
The list of numbers are (5, 4, 3, 2, 1)
Our first choice has 5 possibilities.
The number of orders 5 numbers could be in:
120
```

What we have seen, is a tip of iceberg. In reality, there are hundreds of Combinatorial algorithms that deal with different types of data structures based on finite sets. We can include even structures that are built from graphs.