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


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 > 0:
        print(out)
    if start == in.length:
        return
    for (int i = start; i < in.length; i++):
        out.append(in[i])
        combine(in, out, i +1)
        out.length = out.length -1

Another way works off this logic - to get combinations for ith item, append it to the combinations at i-1th item. This approach needs to store all combinations to work i.e. O(2ⁿ) space.

combination(char[] in):
    list = new list(capacity: 2^in.length)
    list.add("")
    combine(in, list, 0, new buffer())
    return list
    
combine(char[] in, list, index, buffer):
    if index == a.length:
        return
    // capture length before adding elements
    length = list.length
    for i = 0, i < length, i++:
        buffer.clear().append(list[i]).append(in[index])
        list.add(buffer.tostring())
    combine(in, list, index +1, buffer)

Time efficiency is O(2ⁿ).

Another way (bottom up) is to get the combinations for bc (b as ch) as b, b + c, c as:
ch
ch + combine()
combine()

[] combine(in, i = 0):
    if i == s.length():
        return empty
    items = new
    ch = in[i]
    items.add(ch)
    childItems = combine(in, i +1)
    for item in childItems:
        items.add(ch + item)
    for item in childItems:
        items.add(item)
    return items

Similar bottom-up for permute is to get permutations for abc (a as ch and bc, cb as child permutations) as abc, bac, bca by inserting a at every index of bc (0, 1, 2) and same for cb.

[] permute(in, i = 0)
    if i == in.length():
        return [ "" ]
    ch = in[i]
    items = new
    childItems = permute(in, i +1)
    for childItem in childItems:
        buffer = new buffer(childItem)
        for ix = 0, ix <= childItem.length(), ix++:
            buffer.insert(ix, ch)
            items.add(buffer.toString())
            buffer.remove(ix, 1)
    return items

[Hat tip to PIE]


Derivatives:

ⁿC_r: i.e. for abc, print only ab, ac, bc only O(³C₂) = 3.

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

Time efficiency is O(ⁿC_limit).

For abc, print aaa, aab, aac, ... ccc. O(nⁿ) = 3³ = 27.

permutation(char[] in):
    //initially, depth is 0
    permute(in, out, 0)

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

Time efficiency is O(nⁿ).