1 of 14

Permutations

2 of 14

Agenda

  • What are Permutations
  • Implementing Permutations
  • Practice

2

3 of 14

What are Permutations

Counting where order matters

3

1

4 of 14

Permutations

  • Consider 4 students:
    • Aysha, Benji, Ciara, Deepak
  • Write all the ways that the students can be arranged in a line
    • You may want to consider using the initials to make it easier
  • How can you ensure that you got all the arrangements?
    • There are multiple ways to do this

4

5 of 14

Permutations

  • ABCD BACD CABD DABC
  • ABDC BADC CADB DACB
  • ACBD BCAD CBAD DBAC
  • ACDB BCDA CBDA DBCA
  • ADBC BDAC CDAB DCAB
  • ADCB BDCA CDBA DCBA
  • There are 24 distinct ways
  • Can also be written as
    • 4 choices first letter
    • 3 choices second letter (1st already used)
    • 2 choices third letter (1st 2 already used)
    • 1 choice last letter (1st 3 already used)
  • 4!=4x3x2x1=24 by product rule

5

6 of 14

Permutations

​

​

​

  • Factorials are frequently used in counting problems

6

7 of 14

Factorials

  • The first few factorials are

7

8 of 14

Permutations

  • Given n distinct objects
  • They can be arranged in a row of length r in

distinct ways

​

  • These are called the permutations of n
  • Note: this only works when objects are not repeated
    • If there is repetition, divide out the number of repetitions to avoid overcounting

8

9 of 14

Implementing Permutations

One loop might be tricky

9

2

10 of 14

Implementing Permutations

  • Look again at the patterns from permutations of 4 letters
  • ABCD BACD CABD DABC
  • ABDC BADC CADB DACB
  • ACBD BCAD CBAD DBAC
  • ACDB BCDA CBDA DBCA
  • ADBC BDAC CDAB DCAB
  • ADCB BDCA CDBA DCBA
  • Have a loop for the total # of permutations
  • There is a loop to identify each letter in the string for a specific position, remove it, then repeat the process with a smaller string

10

11 of 14

Implementing Permutations

  • Ideally this is done using recursion (soon!)
  • But instead we can use a single loop
    • Mostly, not including loops for factorials
  • We need to keep track of what permutation number we are in
  • Then determine which letter goes in that position
  • Remove the letter and do that again

11

12 of 14

Practice

Trying everything out

12

3

13 of 14

Practice

Find all the permutations of the first n letters

13

14 of 14

CREDITS

Special thanks to all the people who made and released these awesome resources for free:

  • Presentation template by SlidesCarnival

14