- 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();
}
}