Permutations with and without Repetition
Learn the difference between permutations with and without repetition.
We'll cover the following...
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.
/* 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 *///StringPermutationclass Main{// we need a global recursive method// that will print all the permutations of the stringstatic void arrangeTheStringWithRepetition(String anyString, String anotherString){// we need to check if the given string is emptyif (anyString.length() == 0) {System.out.print(anotherString + " ");return;}for (int i = 0; i < anyString.length(); i++) {// reaching to the last characterchar ch = anyString.charAt(i);// we can display the rest of the character after// excluding the last characterString restOfTheString = anyString.substring(0, i) + anyString.substring(i + 1);// calling the method recursivelyarrangeTheStringWithRepetition(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 timesarrangeTheStringWithRepetition(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 ...