Search⌘ K
Home
Courses
Programming Discrete Math Concepts for Beginners

Permutations with and without Repetition

Explore how to generate string permutations with and without repetition by implementing recursive algorithms. Understand the difference in the number of arrangements when repetition is allowed versus when it is not. This lesson helps you grasp the algorithmic logic behind combinatorial string rearrangements and apply it practically in programming.

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 ...