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
by RS  admin@creationpie.com : 1024 x 640


1. Permutation: Introduction
  • Constraint logic: unification and resolution

  • 2. Constraint processing
    Permutation processing is a part of constraint processing that involves determining solutions from a large number of possibilities. 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.

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

    Information sign More: Factorial function
    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? 7 factorialThe 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

    by RS  admin@creationpie.com : 1024 x 640