previous | start | next

## Permutations

- We will design a function that lists all permutations of a string.
- A permutation is simply a rearrangement of the letters:

  >     "eat"
  >     "eta"
  >     "aet"
  >     "ate"
  >     "tea"
  >     "tae"

- If a string has n letters, then the number of permutations is given by the factorial function:

  >     n! = 1 x 2 x 3 x . . . x n

- To a compute the value of a n! you could use a loop (see chapter 7), but there is also a recursive solution:

  >     n! = (n - 1)! x n

- It is customary to define

  >     1! = 1
  >     0! = 0

- You can therefore implement a recursive factorial function as follows:

  >     int factorial(int n)
  >     {
  >        if (n == 0) return 1;
  >        int smaller_factorial = factorial(n - 1);
  >        int result = smaller_factorial * n;
  >        return result;
  >     }

previous | start | next