Search⌘ K
Home/
Courses/
Programming Discrete Math Concepts for Beginners

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.

Java
/* 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 ...