# Permutations, Substrings and Subsequences

Let’s start this article by defining these terms:

**Permutation**: A**permutation**, also called an “arrangement number” or “order” is a re-arrangement of the elements of an ordered list**S**into a one-to-one correspondence with**S**itself.**Substring**: A**substring**is a**contiguous**sequence of characters within a string. The word contiguous is important here as you cannot skip words or characters between the selected words/characters in a substring.**Subsequence**: A**subsequence**is a sequence that can be derived from another sequence (sequence of characters in case of a string) by deleting some or no elements without changing the order of the remaining elements.

#### Examples

- Permutations of the word
**ABC**: {“ABC”, “ACB”, “BAC”, “BCA”, “CBA”, “CAB”} - Substrings of the word
**ABC**are represented as : {“A”, “B”, “C”, “AB”, “BC”, “ABC”}. - Subsequences of the word
**ABC**are represented as : {“A”, “B”, “C”, “AB”, “BC”, “AC”, “ABC”, “”}

#### Fact Check

- The number of permutations of a String of length
**n**is given equal to: $n!$ - The permutations of a string are also known as
**Anagrams**of that string. - The number of non-empty substrings of a string of length
**n**is equal to: $\frac{n(n+1)}{2}$. - A
**prefix**is a substring that is present at the begening of the string and a**suffix**is a substring present at the end of a string. - The number of non-empty subsequences of a string of length
**n**is equal to: $2^{n}-1$ - All the subsequences of a string (including the empty subsequence) together form the power set of that string.

#### Java Implementation

The following is a java implementation to generate all the **permutations** of a string:

```
//total number of permutations returned is input.length()!
public List<String> permutations(String input) {
List<String> permutations = new ArrayList<>();
printPermutations(input, "", permutations);
return permutations;
}
private void printPermutations(String input, String prefix, List<String> permutations) {
if (input.length() == 0) {
//System.out.println(prefix);
permutations.add(prefix);
return;
}
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
String ros = input.substring(0, i) +
input.substring(i + 1);
printPermutations(ros, prefix + ch, permutations);
}
}
```

The following is a java implementation to generate all **substrings** of a string:

```
// the total number of substrings of a string of length n is n(n+1)/2
// so the best case complexity will be n^2; even to list all the substrings
public List<String> generateSubstrings(String input) {
List<String> substrings = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
for (int j = i + 1; j <= input.length(); j++) {
substrings.add(input.substring(i, j));
}
}
return substrings;
}
```

There are multiple approaches to generate the possible subsequences of a string/array. The following are a few java implementations to generate all **subsequences** of a string:

```
// approach-1
// number of substrings for a string of length n is 2^n including blank substring
public List<String> listSubSequences(String input) {
return generate(input, -1, "", new ArrayList<>());
}
private List<String> generate(String input, int currentIndex, String prefix, List<String> subsequences){
if (currentIndex == input.length()) {
return subsequences;
}
subsequences.add(prefix);
for (int i = currentIndex + 1; i < input.length(); i++) {
prefix += input.charAt(i);
generateSubSequences(input, i, prefix, subsequences);
// Once all subsets beginning with initial "curr" are printed, remove
// last character to consider a different prefix of subsets.
prefix = prefix.substring(0, prefix.length() - 1);
}
return subsequences;
}
```

The second approachh is also a recursive approach and is based on the condition to include and not include the current character:

```
//approach-2
public List<String> calculatePowerSet(String input) {
List<String> powerSet = new ArrayList<>();
powerSet(input, 0, "", powerSet);
return powerSet;
}
private void powerSet(String input, int index, String prefix, List<String> powerSet) {
int stringLength = input.length();
// base case
if (index == stringLength) {
powerSet.add(prefix);
return;
}
// Two cases for every character :
// 1. We consider the character as part of current subset
// 2. We do not consider current character as part of current subset
powerSet(input, index + 1, prefix + input.charAt(index), powerSet);
powerSet(input, index + 1, prefix, powerSet);
}
```

There is another approach to generate the subsequences using bitwise operations. As it can be observed that different subsequences of a string are in accordance with the location of setbits in their decimal equivalent numbers generated from 0 to $2^{n}$.

Let’s consider the an example to better understand this. For input=“ABC” with length 3, there are 8 ($2^3$) possible subsequences. These can be represented in terms of the corresponding binary representation of numbers from 0 to 7.

# | Binary Representation | Subsequence |
---|---|---|

0 | 000 | |

1 | 001 | A |

2 | 010 | B |

3 | 100 | C |

4 | 011 | AB |

5 | 101 | AC |

6 | 110 | BC |

7 | 111 | ABC |

A java program to implement the same can be written as follows:

```
//approach-3
private Set<Set<Integer>> generate(int[] input, Set<Set<Integer>> subsets) {
//as number of elements in power set is 2^n
//loop through all the numbers from 0 to 2^n - 1
int numberOfElementsInInputSet = input.length;
for (int currentNumber = 0; currentNumber < (1 << numberOfElementsInInputSet); currentNumber++) {
Set<Integer> subset = new LinkedHashSet<>();
//for every number generated from the first loop,
//check if ith bit is set where 0 <= i < n (n being the size of input array)
for (int currentIndex = 0; currentIndex < numberOfElementsInInputSet; currentIndex++) {
// (1<<j) is a number with jth bit set as 1
// anding the same with i will resultin > 0 only if jth bit is set in i
if ((currentNumber & (1 << currentIndex)) > 0) {
subset.add(input[currentIndex]);
}
}
subsets.add(subset);
}
return subsets;
}
```