10. Combinatorics and Counting, Permutation and Combinations
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 fulfills 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.
1 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.
1 // code 10.1
2
3 package chapterten;
4
5 /**
6 * permutation is a combination of collections where order matters
7 * permutation could be with repetition or without
8 * here we see an example of
9 * permutations without repetition
10 * if there are 16 things, and if we choose 14
11 * then we cannot choose 14 again
12 * in that case, 15 things remain
13 * no repetitions and order matters
14 */
15
16 /**
17 * Here is our problem:
18 * what order could 5 balls be in
19 * for 5 balls the possibility is factorial(5)
20 * if we take any otwo out of it
21 * the possibility is factorial(5 - 3)
22 * but the order of 2 out of 5 balls
23 * is factorial(5) / factorial(5 - 3)
24 */
25
26 public class SimplePermutation {
27
28 static int permutationWithoutRepetition(int n){
29 int i = 1;
30 int k = 1;
31 while (i <= n){
32 k *= i;
33 i++;
34 }
35 //we get the factorial of the number we have passed as parameter
36 return k;
37 }
38
39 public static void main(String[] args) {
40
41 /**
42 * the formula of permutation without repetition
43 * is factorial(listOfNumbers)/factorial(listOfNumbers - restOfNumbers)
44 */
45 int listOfNumbers = 5;
46 int restOfNumbers = 3;
47 System.out.println("The list of numbers are (5, 4, 3, 2, 1)");
48 System.out.println("Our first choice has 5 possibilities.");
49 System.out.println("The number of orders 5 numbers could be in: ");
50 System.out.println(permutationWithoutRepetition(5));
51 }
52 }
The output is quite expected. When 5 things are to be rearranged, there are 120 possibilities, which is actually the factorial of 5.
1 // output of 10.1
2
3 The list of numbers are (5, 4, 3, 2, 1)
4 Our first choice has 5 possibilities.
5 The number of orders 5 numbers could be in:
6 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. We will talk about them in a few minutes, but before that, 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.
1 // code 10.2
2
3 package chapterten;
4
5 /**
6 * permutation is a combination of collections where order matters
7 * permutation could be with repetition or without
8 * here we see an example of
9 * permutations without repetition
10 * if there are 16 things, and if we choose 14
11 * then we cannot choose 14 again
12 * in that case, 15 things remain
13 * no repetitions and order matters
14 */
15
16 /**
17 * Here is our problem:
18 * what order could 5 balls be in
19 * for 5 balls the possibility is factorial(5)
20 * if we take any otwo out of it
21 * the possibility is factorial(5 - 3)
22 * but the order of 2 out of 5 balls
23 * is factorial(5) / factorial(5 - 3)
24 */
25
26 public class SimplePermutation {
27
28 static int permutationWithoutRepetition(int n){
29 int i = 1;
30 int k = 1;
31 while (i <= n){
32 k *= i;
33 i++;
34 }
35 //we get the factorial of the number we have passed as parameter
36 return k;
37 }
38
39 public static void main(String[] args) {
40
41 /**
42 * the formula of permutation without repetition
43 * is factorial(listOfNumbers)/factorial(listOfNumbers - restOfNumbers)
44 */
45 int listOfNumbers = 5;
46 int restOfNumbers = 3;
47 System.out.println("The list of numbers are (5, 4, 3, 2, 1)");
48 System.out.println("Our first choice has 5 possibilities.");
49 System.out.println("The number of orders 5 numbers could be in: ");
50 System.out.println(permutationWithoutRepetition(5));
51 System.out.println("Now we need any two numbers from this collection:");
52 System.out.println("The order of 2 numbers out of 5 numbers could be: ");
53 System.out.println(permutationWithoutRepetition(5)/permutationWithoutRepetit\
54 ion(3));
55
56 }
57 }
Here is the explanation. When we pick up 2 elements from 5 elements, 3 elements are left behind. The algorithm is quite simple.
1 First, find out the factorial of 5.
2 Second, find out the factorial of 3.
3 Third, divide factorial of 5 by factorial of 3.
We have done the same thing. And here is the output:
1 // output of 10.2
2
3 The list of numbers are (5, 4, 3, 2, 1)
4 Our first choice has 5 possibilities.
5 The number of orders 5 numbers could be in:
6 120
7 Now we need any two numbers from this collection:
8 The order of 2 numbers out of 5 numbers could be:
9 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.
1 // code 10.3
2
3 package chapterten;
4
5 /**
6 * When repetition is allowed, we can rearrange the order
7 * of a string in various combination
8 * since we will keep the order with repetitions,
9 * we can call it a permutation of a string
10 */
11
12 public class StringPermutation {
13 // we need a global recursive method
14 // that will print all the permutations of the string
15 static void arrangeTheStringWithRepetition(String anyString, String anotherStrin\
16 g){
17
18 // we need to check if the given string is empty
19 if (anyString.length() == 0) {
20 System.out.print(anotherString + " ");
21 return;
22 }
23
24 for (int i = 0; i < anyString.length(); i++) {
25
26 // reaching to the last character
27 char ch = anyString.charAt(i);
28
29 // we can display the rest of the character after
30 // excluding the last character
31 String restOfTheString = anyString.substring(0, i) +
32 anyString.substring(i + 1);
33
34 // calling the method recursively
35 arrangeTheStringWithRepetition(restOfTheString, anotherString + ch);
36 }
37 }
38
39 public static void main(String[] args) {
40
41 String stringToArrange = "abcd";
42 // the given string 'abcd' is of length 4
43 // factors of 4 is 4,3,2,1
44 // factorial is 24
45 // the program will rearrange the string 24 times
46 arrangeTheStringWithRepetition(stringToArrange, " ");
47 System.out.println();
48
49 }
50
51 }
52
53
54 // output of 10.3
55
56 abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb \
57 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 could be allowed.
In a given string where the length is 3, we can rearrange that string in 6 ways, which is the factorial of 3. What happens, when repetition is not allowed.
1 // code 10.4
2
3
4 package chapterten;
5
6 /**
7 * When repetition is not allowed to arrange a given string
8 * our scope is limited, consider an example
9 * for a combination lock, where the given numbers are from
10 * 0 to 10, and we are told to choose any three numbers,
11 * we cannot use arrangement like 111
12 */
13
14 public class StringPermutationWithoutRepetition {
15
16 // we need a global method, where we will arrange a string
17 // without repeating a sequence more than once
18 static void displayingDistinctString(String anyString, String anotherString){
19
20 // we need to check if the given string is empty
21 if (anyString.length() == 0) {
22 System.out.print(anotherString + " ");
23 return;
24 }
25
26 // keeping in mind that we have 26 alphabets we need a
27 // boolean array of size '26'
28 boolean allAlphabets[] = new boolean[26];
29
30 for (int i = 0; i < anyString.length(); i++) {
31
32 // reaching to the last character
33 char ch = anyString.charAt(i);
34
35 // we can display the rest of the character after
36 // excluding the last character
37 String restOfTheString = anyString.substring(0, i) +
38 anyString.substring(i + 1);
39
40 // it will check the repetition, if the character has already been used,
41 // it will call the method recursively; else, there will be no recursive\
42 call
43 if (allAlphabets[ch - 'a'] == false)
44 displayingDistinctString(restOfTheString, anotherString + ch);
45 allAlphabets[ch - 'a'] = true;
46 }
47 }
48
49 public static void main(String[] args) {
50
51 String stringToArrangeWithoutRepeating = "bbc";
52
53 displayingDistinctString(stringToArrangeWithoutRepeating, " ");
54 System.out.println();
55
56 }
57 }
58
59
60 // output of 10.4
61
62 bbc bcb cbb
To test the above code, we have used a string where one character ‘b’ has been used twice. As a matter of fact, if repeating is allowed, there could be 6 rearrangements.
Since, repeating is not allowed, we get the above output. Just before, in the code 10.3, we have seen an algorithm where repetition has been allowed, and accordingly we have seen the rearrangements.
We can do the same in a different way. We can rearrange the sequence of characters in such a way so that the string output would be of various orders. Some of them may look similar because we have allowed repetition.
1 // code 10.5
2
3 package chapterten;
4
5 import java.util.Scanner;
6
7 public class StringPermutationWithRepetition {
8
9 // we need a global method to swap two characters
10 // and return the string in a sequential array
11
12 static String swappingCharacters(String aString, int i, int j){
13
14 char aCharacter;
15
16 char[] sequentialArray = aString.toCharArray();
17
18 aCharacter = sequentialArray[i];
19
20 sequentialArray[i] = sequentialArray[j];
21
22 sequentialArray[j] = aCharacter;
23
24 return String.valueOf(sequentialArray);
25
26 }
27
28 // a method to display every combination of arrangement of the string
29 // in order, where repetition is allowed
30
31 static void permuteAStringByRepeating(String aString, int start, int finish){
32
33 if(start == finish){
34
35 System.out.println(aString);
36
37 }
38 int i;
39
40 for(i = start; i <= finish; i++){
41
42 aString = swappingCharacters(aString, start, i);
43
44 permuteAStringByRepeating(aString, start + 1, finish);
45
46 aString = swappingCharacters(aString, start, i);
47
48 }
49
50 }
51
52 public static void main(String[] args) {
53
54 Scanner sc = new Scanner(System.in);
55 System.out.println("Enter a string to see all possible permutations where re\
56 petition is allowed: ");
57 String enterAString;
58 enterAString = sc.next();
59 System.out.println("It arranges the string '" + enterAString + "' according \
60 to the number of factorials" +
61 " of its length.");
62 permuteAStringByRepeating(enterAString, 0, enterAString.length() - 1);
63 System.out.println();
64 }
65 }
Since the length of the string is 3, the factorial of 3 would give us the desired number. Factorial of 3 is 6, therefore, we have 6 arrangements in place.
1 // output of 10.5
2
3 Enter a string to see all possible permutations where repetition is allowed:
4 aab
5 It arranges the string 'aab' according to the number of factorials of its length.
6 aab
7 aba
8 aab
9 aba
10 baa
11 baa
There are hundreds of other Combinatorial problems and algorithms. To get our head around them to understand the inner logic, we need practice. Furthermore, we need to keep the issue of time complexity in our mind, at the same time.
I write regularly on Algorithm and Data Structure in
QUIZZ on Chapter ten
Question 1: The key abstractions of Combinatorics depend on permutations and combinations.
Option 1: True
Option 2: False
Answer: Option 1
========================
Question 2: When order does not matter in a combination, it is called permutation.
Option 1: The above statement is true and can be proved in any programming language.
Option 2: The above statement is true mathematically, but we cannot implement it in any programming language.
Option 3: The above statement is neither true mathematically, nor we can implement it in any programming language.
Option 4: None of the above statement is true.
Answer: Option 4.
=======================
Question 3: A string is a sequence of characters. It is a representation of data structure, an array of characters.
Option 1: True
Option 2: False
Answer: Option 1
========================
Question 4: Search algorithms are good examples where Optimization and Approximation algorithms are used to solve such problems.
Option 1: The above statement is partly true.
Option 2: The above statement is does not make any sense.
Option 3: The above statement is absolutely true.
Option 4: None of the above statement is true.
Answer: Option 3.
=======================
Question 5: There are hundreds of Combinatorial algorithms.
Option 1: True
Option 2: False
Answer: Option 1
=======================
Challenge 1 : How many ways we can rearrange 5 balls.
Solution to Challenge 1:
Language Used: Java
1 //code
2
3 public class SimplePermutation {
4
5 static int permutationWithoutRepetition(int n){
6 int i = 1;
7 int k = 1;
8 while (i <= n){
9 k *= i;
10 i++;
11 }
12 //we get the factorial of the number we have passed as parameter
13 return k;
14 }
15
16 public static void main(String[] args) {
17
18 /**
19 * the formula of permutation without repetition
20 * is factorial(listOfNumbers)/factorial(listOfNumbers - restOfNumbers)
21 */
22 int listOfNumbers = 5;
23 int restOfNumbers = 3;
24 System.out.println("The list of numbers are (5, 4, 3, 2, 1)");
25 System.out.println("Our first choice has 5 possibilities.");
26 System.out.println("The number of orders 5 numbers could be in: ");
27 System.out.println(permutationWithoutRepetition(5));
28 }
29 }
30
31
32 // When 5 things are to be rearranged, there are 120 possibilities, which is actuall\
33 y the factorial of 5.
34
35
36 // output of 10.1
37
38 The list of numbers are (5, 4, 3, 2, 1)
39 Our first choice has 5 possibilities.
40 The number of orders 5 numbers could be in:
41 120
Challenge 2 : Suppose you have a string “abcd”. You are aked to rearrange the String. How many ways could you rearrange the String when repetition is allowed? Here repetition means, you can rearrange this way: bacd, cdba, dbac, etc.
Solution to Challenge 3:
Language Used: Java
1 // code
2
3 package chapterten;
4
5 /**
6 * When repetition is allowed, we can rearrange the order
7 * of a string in various combination
8 * since we will keep the order with repetitions,
9 * we can call it a permutation of a string
10 */
11
12 public class StringPermutation {
13 // we need a global recursive method
14 // that will print all the permutations of the string
15 static void arrangeTheStringWithRepetition(String anyString, String anotherStrin\
16 g){
17
18 // we need to check if the given string is empty
19 if (anyString.length() == 0) {
20 System.out.print(anotherString + " ");
21 return;
22 }
23
24 for (int i = 0; i < anyString.length(); i++) {
25
26 // reaching to the last character
27 char ch = anyString.charAt(i);
28
29 // we can display the rest of the character after
30 // excluding the last character
31 String restOfTheString = anyString.substring(0, i) +
32 anyString.substring(i + 1);
33
34 // calling the method recursively
35 arrangeTheStringWithRepetition(restOfTheString, anotherString + ch);
36 }
37 }
38
39 public static void main(String[] args) {
40
41 String stringToArrange = "abcd";
42 // the given string 'abcd' is of length 4
43 // factors of 4 is 4,3,2,1
44 // factorial is 24
45 // the program will rearrange the string 24 times
46 arrangeTheStringWithRepetition(stringToArrange, " ");
47 System.out.println();
48
49 }
50
51 }
52
53
54 // output
55
56 abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb \
57 cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba
Challenge 3 : Can you show the difference between two types of permutation,where repetition is not allowed and allowed.
Solution to Challenge 3:
Language Used: Java
1 // when reprtition is not allowed
2
3 // code
4
5
6 package chapterten;
7
8 /**
9 * When repetition is not allowed to arrange a given string
10 * our scope is limited, consider an example
11 * for a combination lock, where the given numbers are from
12 * 0 to 10, and we are told to choose any three numbers,
13 * we cannot use arrangement like 111
14 */
15
16 public class StringPermutationWithoutRepetition {
17
18 // we need a global method, where we will arrange a string
19 // without repeating a sequence more than once
20 static void displayingDistinctString(String anyString, String anotherString){
21
22 // we need to check if the given string is empty
23 if (anyString.length() == 0) {
24 System.out.print(anotherString + " ");
25 return;
26 }
27
28 // keeping in mind that we have 26 alphabets we need a
29 // boolean array of size '26'
30 boolean allAlphabets[] = new boolean[26];
31
32 for (int i = 0; i < anyString.length(); i++) {
33
34 // reaching to the last character
35 char ch = anyString.charAt(i);
36
37 // we can display the rest of the character after
38 // excluding the last character
39 String restOfTheString = anyString.substring(0, i) +
40 anyString.substring(i + 1);
41
42 // it will check the repetition, if the character has already been used,
43 // it will call the method recursively; else, there will be no recursive\
44 call
45 if (allAlphabets[ch - 'a'] == false)
46 displayingDistinctString(restOfTheString, anotherString + ch);
47 allAlphabets[ch - 'a'] = true;
48 }
49 }
50
51 public static void main(String[] args) {
52
53 String stringToArrangeWithoutRepeating = "bbc";
54
55 displayingDistinctString(stringToArrangeWithoutRepeating, " ");
56 System.out.println();
57
58 }
59 }
60
61
62 // output
63
64 bbc bcb cbb
65
66 // when repetiiton is allowed
67
68 // code
69
70 package chapterten;
71
72 import java.util.Scanner;
73
74 public class StringPermutationWithRepetition {
75
76 // we need a global method to swap two characters
77 // and return the string in a sequential array
78
79 static String swappingCharacters(String aString, int i, int j){
80
81 char aCharacter;
82
83 char[] sequentialArray = aString.toCharArray();
84
85 aCharacter = sequentialArray[i];
86
87 sequentialArray[i] = sequentialArray[j];
88
89 sequentialArray[j] = aCharacter;
90
91 return String.valueOf(sequentialArray);
92
93 }
94
95 // a method to display every combination of arrangement of the string
96 // in order, where repetition is allowed
97
98 static void permuteAStringByRepeating(String aString, int start, int finish){
99
100 if(start == finish){
101
102 System.out.println(aString);
103
104 }
105 int i;
106
107 for(i = start; i <= finish; i++){
108
109 aString = swappingCharacters(aString, start, i);
110
111 permuteAStringByRepeating(aString, start + 1, finish);
112
113 aString = swappingCharacters(aString, start, i);
114
115 }
116
117 }
118
119 public static void main(String[] args) {
120
121 Scanner sc = new Scanner(System.in);
122 System.out.println("Enter a string to see all possible permutations where re\
123 petition is allowed: ");
124 String enterAString;
125 enterAString = sc.next();
126 System.out.println("It arranges the string '" + enterAString + "' according \
127 to the number of factorials" +
128 " of its length.");
129 permuteAStringByRepeating(enterAString, 0, enterAString.length() - 1);
130 System.out.println();
131 }
132 }
133
134 // output
135
136 Enter a string to see all possible permutations where repetition is allowed:
137 aab
138 It arranges the string 'aab' according to the number of factorials of its length.
139 aab
140 aba
141 aab
142 aba
143 baa
144 baa