https://leanpub.com/discretemathematicalalgorithmanddatastructures

Let us see some common examples of Combinatorial algorithms. We can think of generating list of all structures of a given type. In this scenario, we can think of permutation with repetition, or without repetition. We can think of combinations with repetition, or without repetition.

Search algorithms are good examples where Optimization and Approximation algorithms are used to solve such problems. Optimization methods or algorithms also include dynamic programming. On the other hand, Approximation methods include greedy algorithms.

We cannot say that one algorithm is the best solution. There could be a better algorithm than the previously claimed ‘best’.

Let us solve a problem and see whether the solution is best or not.

There are five things. We have found out that if there are five things, there could be 120 possibilities. Let us pick any two of them and try to rearrange them in order. However, we cannot repeat the same thing twice. It is a permutation without repetition, still it is little bit different.

If we want to rearrange any two things from that five elements without repetition, what would be the order.

```
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));
System.out.println("Now we need any two numbers from this collection:");
System.out.println("The order of 2 numbers out of 5 numbers could be: ");
System.out.println(permutationWithoutRepetition(5)/permutationWithoutRepetition(3));
}
}
```

Here is the explanation. When we pick up 2 elements from 5 elements, 3 elements are left behind. The algorithm is quite simple.

First, find out the factorial of 5.

Second, find out the factorial of 3.

Third, divide factorial of 5 by factorial of 3.

We have done the same thing. And here is the output:

```
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
Now we need any two numbers from this collection:
The order of 2 numbers out of 5 numbers could be:
20
```

As we have said earlier, there are hundreds of Combinatorial algorithms. Besides more common ‘sorting’ and ‘searching’, we have different types of generating ‘permutations and combinations’, graphs, and many others.

Our next problem will deal with some kind of generating permutation and combination. How many ways we can rearrange a string? If repetition is allowed, it is obvious that number of rearrangement will be more.

How it happens?

A string is a sequence of characters. It is a representation of data structure, an array of characters.

Therefore, it has a length. If repetition is allowed, we can count the length of the string, and safely say that the factorial of that number is the possibility.

But the real trick is in the process of rearrangement.

```
package chapterten;
/**
* When repetition is allowed, we can rearrange the order
* of a string in various combination
* since we will keep the order with repetitions,
* we can call it a permutation of a string
*/
public class StringPermutation {
// we need a global recursive method
// that will print all the permutations of the string
static void arrangeTheStringWithRepetition(String anyString, String anotherString){
// we need to check if the given string is empty
if (anyString.length() == 0) {
System.out.print(anotherString + " ");
return;
}
for (int i = 0; i < anyString.length(); i++) {
// reaching to the last character
char ch = anyString.charAt(i);
// we can display the rest of the character after
// excluding the last character
String restOfTheString = anyString.substring(0, i) +
anyString.substring(i + 1);
// calling the method recursively
arrangeTheStringWithRepetition(restOfTheString, anotherString + ch);
}
}
public static void main(String[] args) {
String stringToArrange = "abcd";
// the given string 'abcd' is of length 4
// factors of 4 is 4,3,2,1
// factorial is 24
// the program will rearrange the string 24 times
arrangeTheStringWithRepetition(stringToArrange, " ");
System.out.println();
}
}
// output
abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba
```

In the above code snippet, the string is of length 4.

Therefore, factorial of 4, that is 24 is the number of possibility. The above program rearranges the string 24 ways. However, the condition was repetition was allowed.