Permutation of given string

Question

I am reading a book on DSA, and the author explains how to generate the permutation of strings using recursion. I want to know if there are better ways of doing the same, unless this is the best solution. Also, could someone help me understand the time-complexity of this algorithm? Recursion is something I use very rarely but am trying to learn about now.

public class Anagrams {
private char[] chArray;
private int size;
private static int count;

public Anagrams(String anagramString, int size) {
    if (size <= 0) {
        System.out.println("Please enter a valid String");
    }
    chArray = anagramString.toCharArray();
    this.size = size;

}

public static void main(String args[]) {
    String str = "dogs";
    Anagrams anagramGenerator = new Anagrams(str, str.length());
    anagramGenerator.generateAnagrams(str.length());

}

public void generateAnagrams(int newSize) {
    if (newSize == 1)
        return;

    for (int i = 0; i < newSize; i++) {
        generateAnagrams(newSize - 1);
        if (newSize == 2)
            displayWord();
        rotate(newSize);
    }

}

private void rotate(int newSize) {
    // TODO Auto-generated method stub
    int position = size - newSize;
    char tempCh = chArray[position];
    int i;
    for (i = position + 1; i < size; i++) {
        chArray[i - 1] = chArray[i];
    }
    chArray[i - 1] = tempCh;

}

private void displayWord() {
    // TODO Auto-generated method stub
    String word = "";
    count++;
    for (int i = 0; i < chArray.length; i++) {
        word += chArray[i];
    }
    System.out.println(count + ")" + word);
}
}

Answer 1

Be consistent

The most important advice I could give you is be consistent. Be consistent with your naming convention, the placement of brackets and everything else. Why ? Because even if you're doing something wrong you will be predictable, and that is what make things faster when reviewing.

   if (size <= 0) {
        System.out.println("Please enter a valid String");
   } 

vs

 if (newSize == 1)
        return;

Same situation, an if condition and one line of code if the condition is good. Why one have brackets and the other one don't have it ? In this particular case, always use brackets. It's more readable, if you add a line of code you don't have to add brackets and it will probably reduce the chance to have bugs.

Constructor

public Anagrams(String anagramString, int size)

You already using String as parameter, why do you have size ? When you call your constructor, you're passing str.lenght(). I suggest that you drop the second argument and just call the length directly in your constructor.

public Anagrams(String anagramString) {
    if (size <= 0) {
        System.out.println("Please enter a valid String");
    }
    chArray = anagramString.toCharArray();
    this.size = anagramString.lenth();

}

Another important point, you're checking if the size <= 0 and print that you must enter a valid String, but you don't do nothing else. The program will go on in an invalid state. You could throw an exception that specify that the length of the String must be greater than 0.

Comments

Never leave // TODO Auto-generated method stub comments. It's just noise in the code, and could lead to people thinking that your code is somewhat not finished.

Answer 2

• The rotate function which reverses a sequence can be done in O(n/2) strictly it is still O(n) but when it is used a lot, then it's better to optimize it.
• The displayWord function is O(n²). It can be made constant by passing the array as argument. If StringBuilder is used with append, it can be O(n).

• generateAnagrams G(n) = O(1) + (n-1)*(G(n-1) + O(n) + O(1)). This complexity is kind of difficult to calculate, I ran it on WolphramAlpha. If you understand the Gamma function, then go ahead and click. I did narrow down the complexity to Ω(e.n!) (NB: not theta, or Big O but Omega) by running the following code and OEISWiki;

  e is the exponential constant and n! is the factorial of n.

.

bool compute(int i, int &c ){
        c++;
        if(i==0) return true;
        for(int j=0; j<i; j++)
                compute(i-1,c);
        return true;
}

int main(){
        for(int i=0; i<11; i++){
                int c = 0;
                compute(i,c);
                cout<<c<<", ";
        }
}

UPDATE Your code doesn't treat the case where a character occurs more than once. For example it returns 120 for "dogss" instead of 60.

Permutations can be generated by searching for the next array lexicographically greater than the current one, containing the same characters. Check Wikipedia. This is used in C++i in the function next_permutation. Given a string "dogs", the next permutation would be dosg. Which means that if we are to sort an array containing all possible permutation of the word dogs, we will get the same order given by this method. The problem with this method is that the array/word must be sorted in order to get all possible permutation, if not then the function will print out permutations starting only from the current word.

The algorithm is simple

1.    if length of word is 0 or 1 then return false
2.    if not
3.       from the right, find the first two ascending characters
4.          if found, take the left one
5.             from the right, find the first character greater than it,
6.             swap them
7.             then reverse all characters from the right one to the end
8.             return true
9.          if not found, return false

Observe that after line 3, the sequence formed from the right one to the far left is a non increasing sequence, so after the swap in 6, there is a need to reverse to keep the order of permutation strict (we are looking for the next greater permutation after all). In the worst case, supposing that the ascending characters are always found int far right, the the complexity of this algorithm is O(n.n!), since it is called n! times

import java.util.Arrays;

public class Permutation {
    private char[] word;
    private long count;

    public Permutation(char[] _word) {
        word = _word;
        count = 0;
    }

    boolean permute() {
        while (nextPermutation())
            ;
        return true;
    }

    void print() {
        System.out.print(++count);
        System.out.print(". ");
        System.out.println(word);
    }

    boolean nextPermutation() {
        print();
        int next = word.length;
        if (next-- <= 1)
            return false;
        for (;;) {
            int next1 = next;
            if (word[--next] < word[next1]) {
                int mid = word.length;
                for (; !(word[next] < word[--mid]);)
                    ;
                swap(next, mid);
                reverse(next1, word.length);
                return true;
            }
            if (next == 0)
                return false;
        }
    }

    boolean swap(int left, int right) {
        char c = word[right];
        word[right] = word[left];
        word[left] = c;
        return true;
    }

    boolean reverse(int first, int last) {
        // reverse elements in [first, last)
        for (; first != last && first != --last; ++first)
            swap(first, last);
        return true;
    }

    public static void main(String args[]) {
        String str = "dogs";
        char[] word = str.toCharArray();
        Arrays.sort(word);
        Permutation permuteWord = new Permutation(word);
        permuteWord.permute();
    }
}