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

^{n}) 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^{n}).

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:

^{n}C

_{r}: i.e. for

`abc`

, print only `ab`

, `ac`

, bc only O(^{3}C

_{2}) = 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(^{n}C

_{limit}).

For

`abc`

, print `aaa`

, `aab`

, aac, ... ccc. O(n^{n}) = 3

^{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^{n}).

## No comments:

## Post a Comment