Send
Close Add comments:
(status displays here)
Got it! This site "creationpie.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.
Permutation: Introduction
1. Permutation: Introduction
2. Constraint processing
Permutation processing is a part of constraint processing that involves determining solutions from a large number of possibilities.
finite domains
real number domains
These possibilities involve combinations, permutations, etc. The general name for this field is combinatorial optimization.
3. Permutations
A
permutation is an arrangement of distinct objects where the order of the objects is important.
How many ways are there to arrange the letters
a,
b, and
c?
4. Reasoning
Here is the reasoning.
There are 3 ways to pick the first letter, which leaves two letters remaining.
There are 2 ways to pick the second letter, which leaves one letter remaining.
There is 1 way to pick the third (i.e., last) letter, which leaves no letters remaining.
5. Enumeration
Here are the permutations.
a b c
a c b
b a c
b c a
c a b
c b a
6. Letter arrangements
For
3 letters, there are
3*2*1
ways to arrange them.
7. Generalization
In general, if there are
n objects, then there are
n ways to pick the first object,
n-1 ways to pick the second object,
n-2 ways to pick the third object,
... until there is ...
1 way to pick the final object.
Using the product rule, we multiply all of the ways together to get total number of permutations.
8. Factorial function
The
factorial function (
!), sometimes called the permutation function since it provides the number of permutations of
n objects, is defined as follows.
0! = 1 (by definition)
n! = n * (n-1)!
= n * (n-1) * (n-2)!
= n * (n-1) * (n-2) * (n-3)!
= n * (n-1) * (n-2) * (n-3) * ... * 1
9. Identity permutation
What is 0!?
10. Convention
By convention, 0! is 1, since there is only one way to arrange zero objects, by doing nothing.
Technically, taking 0! as 1 (i.e., the multiplicative identity element) makes the math work out easier.
11. Tires
How many ways are there to arrange
4 tires on an automobile?
Assume that there is only one way to put a tire on an automobile (e.g., the whitewall facing out).
12. Tires
There are
4! =
4*3*2*1 =
24 ways to arrange
4 tires on an automobile.
13. Factorial function
The factorial function can be used to calculate the number of permutations of
n objects. The mathematical definition is as follows, using "
*" for multiplication.
fact(0) = 1
fact(n) = n * fact(n-1) , n > 0
Do you see a way to program the factorial function (top-down) using this definition?
Note that this definition is recursive in that it refers to itself.
The factorial function grows quickly.
n! = n * (n-1) * (n-2) * ... * 1
0! = 1
1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120
6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5,040
...
10! is more than 3,600,000
Do you see a way to program the factorial function bottom-up using the above pattern?
The factorial function grows rapidly. Here is a graphical depiction of
7! = 5,040.
59! is about 1080
1080is the number of baryons (electrons, protons, neutrons, etc.) in the known universe.
14. Main program
The main program code is the same for both versions of the code.
15. Iterative function
Here is an iterative factorial function (bottom up version).
It is called "iterative" because it has a loop. Pure recursive functions use recursion instead of loops, using recursion to do iteration.
16. Program
Here is the C code [#3]
17. Output
Here is the output of the C code.
18. Recursive function
Here is the recursive factorial function.
Here is the math definition, using "
*" for multiplication.
fact(0) = 1
fact(n) = n * fact(n-1) , n ≠ 0
19. Recursive function
Here is the same recursive factorial function written slightly differently.
The return is done at the end of the function.
20. Recursive function
Here is the same program using a recursive function (the first one).
Here is the C code [#6]
21. Output
Here is the output of the C code.
22. Tail recursion
Technical note: Tail recursion in the recursive version makes it easy to convert to iteration.
This improvement can be used in functional language, logic languages, and imperative languages.
This saves time and space since it avoids extra push and pops of the stack.
23. Redundant calculations
Problem: Redundant calculations are done.
Solution: Use memoization (behind the scenes) by trading more memory space for less computation time.
Memoization is from the Latin word "
memorandum" which comes from the Greek «
μνεμονικόυς» from the
PIE (Proto Indo-European) for "
men" or "
think" (comment, amnesia, mental, memento, etc.).
Memoization is often done for compiled regular expressions, SQL queries, etc. Space can be traded for time by using the hash of the text and not the text itself.
The browser cache is a form of memoization.
24. End of page