...

/

Permutations with and without Repetition

Permutations with and without Repetition

Learn the difference between permutations with and without repetition.

Reordering a string with repetition

Our next problem deals with generating permutations and combinations. How many ways can we rearrange a string? If repetition is allowed, the number will be large. How does this happen?

A string is a sequence of characters. It’s 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 number of ways a string can be rearranged. But the real trick is how rearrangement works.

Press + to interact
/* When repetition is allowed, we can rearrange the order
* of a string in various combinations
* since we will keep the order with repetitions,
* we can call it a permutation of a string */
//StringPermutation
class Main{
// 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 are 4,3,2,1
// factorial is 24
// the program will rearrange the string 24 times
arrangeTheStringWithRepetition(stringToArrange, " ");
System.out.println();
}
}

We get the following output when we run the code above:

 abcd  abdc  acbd  acdb  adbc  adcb  bacd  badc  bcad  bcda  bdac  bdca  cabd  cadb  cbad  cbda  cdab  cdba  dabc  dacb  dbac  dbca  dcab  dcba 

The code above implements a recursive algorithm to generate all possible permutations of a given string with repetitions allowed.

  • Line 10–27: It defines a static method called arrangeTheStringWithRepetition() that takes two string parameters: anyString, which represents the remaining characters to be arranged, and ...