# 8.7. Permutations without duplicates

> Write a method to compute all permutations of a string of unique characters

* s = anebz
* s = an, size=2
    - permutations = an, na
    - total 4
* s = ane, size=3
    - permutations = ean, ane, ena, nae + aen + nea
    - total 6, 3\*2
* s = aneb, size=4
    - permutations = aneb, anbe, aben, abne, aenb, aebn
    - baen, bane, bean, bena, bnae, bnea
    - eabn, eanb, eban, ebna, enab, enba
    - nabe, naeb, nbae, nbea, neab, neba
    - total 24, 4\*3\*2

In each iteration, add the new word in each position of the previous permutations. for 'an' and new letter 'e', it becomes ean, aen, ane.

```python
def permutations(s):
    prm = [s[0]]
    for char in s[1:]:
        for p in list(prm):
            for i in range(len(p)):
                prm.append(p[:i] + char + p[i:])
    return prm
```

This would have complexity of O(len(s)!) for each character in s. Therefore O(n * n!) = O((n+1)!). Checked example 12 on p51 and it's correct (section 1.9 in the [Introduction](../introduction.md))

## Hints

The hints describe what I have done =) Insert the new letter into each possible location of the previous permutations. You can create all permutations of abcd by computing all permutations of abc and then inserting d into each possible location within those.

```python
# approach 1: building from permutations of first n-1 characters
def permutations(s):
    prm = []
    if len(s) == 0:
        prm.append("")
        return prm
    for word in permutations(s[1:]):
        for i in range(len(word)):
            prm.append(word[:i] + s[0] + word[i:])
    return prm

print(permutations("str"))
```

For a word like 'str', it goes deep into the function until len(s) == 0, then returns '', we go up to 'r', and adds 'r' to each position. We end up with 'r'. Go up, iterate prm ('r') and add 't' to each position. And so on.
