Permutations and Combinations of string

Permutations of string:

For a string of length n, there are n! permutations. For string abcd, there are 24 permutations. We would have a wrapper permutation method which takes the string and calls the recursive permute method. The basic idea is that the permutations of string abc are a + permutations of string bc, b + permutations of string ac and so on. The permute method uses a bool[] used to indicate which characters of the string are already used in the buffer out (to avoid repetitions). The variable depth is used to indicate how many characters of the string in are used in the out buffer. When depth would be equal to length of string in, we print the permutation and return.


permutation(char[] in):
    //initially, used[] set to false and depth is 0
    permute(in, out, used, 0)

permute(char[] in, buffer out, bool[] used, int depth):
    if depth = in.length:
        print out
        return
    for (int i = 0; i < in.length; i++):
        if used[i] = true:
            continue
        used[i] = true
        out.append(in[i])
       
        permute(in, used, out, depth +1)
       
        out.length = out.length -1
        used[i] = false


Time efficiency is O(n^n).


Combinations of string:

For a string of length n, there are nCn + nCn-1 + ... + nC1 combinations. For string abc, there are 1 + 3 + 3 = 7 combinations. We would have a wrapper combination method which takes the string and calls the recursive combine method. The basic idea is that the combinations of string abc are a, a + combinations of string bc and so on. We put the character in the buffer, print it and combine from the next character (i +1) as start for the next combine call. For string ab, it would print a, ab, b in that order. Since the if block just returns when start = in.length, we can optimize the code by calling the combine method in the for loop only when i < in.length -1.


combination(char[] in):
    //initially, start is 0
    combine(in, out, 0)
   
combine(char[] in, buffer out, start):
    if start = in.length:
        return
    for (int i = start; i < in.length; i++):
        out.append(in[i])
        print out
       
        combine(in, out, i +1)
       
        out.length = out.length -1


Time efficiency is O(n^n).