c  go  java  js  lua  py  vbs  rkt  scm  pro  

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.

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?

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.

Here are the permutations.

For 3 letters, there are

ways to arrange them.

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.

The factorial function (!), sometimes called the permutation function since it provides the number of permutations of n objects, is defined as follows.

What is 0!?

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.

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

There are 4! = 4*3*2*1 = 24 ways to arrange 4 tires on an automobile.

The factorial function can be used to calculate the number of permutations of n objects. The mathematical definition is as follows, using "*" for multiplication.

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.

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.

10⁸⁰is the number of baryons (electrons, protons, neutrons, etc.) in the known universe.

The main program code is the same for both versions of the code.
int f1; printf("Factorials:\n"); for (int i1=0; i1 <= 10; i1++) { f1 = fact(i1); printf("\t%d! is %d\n",i1,f1); }

Here is an iterative factorial function (bottom up version).
int fact(int n1) { int f1 = 1; while (n1 != 0) { f1 *= n1; n1--; } return f1; }
It is called "iterative" because it has a loop. Pure recursive functions use recursion instead of loops, using recursion to do iteration.

Here is the C code.
#include <stdio.h> // iterative factorial function int fact(int n1) { int f1 = 1; while (n1 != 0) { f1 *= n1; n1--; } return f1; } int main() { int f1; printf("Factorials:\n"); for (int i1=0; i1 <= 10; i1++) { f1 = fact(i1); printf("\t%d! is %d\n",i1,f1); } return 0; }
Here is the output of the C code.
Factorials: 0! is 1 1! is 1 2! is 2 3! is 6 4! is 24 5! is 120 6! is 720 7! is 5040 8! is 40320 9! is 362880 10! is 3628800

Here is the recursive factorial function.
int fact(int n) { if (n == 0) { return 1; } else { return n * fact(n-1); } }
Here is the math definition, using "*" for multiplication.

Here is the same recursive factorial function written slightly differently.
int fact(int n) { int f1 = 1; if (n == 0) { f1 = 0; } else { f1 = n * fact(n-1); } return f1; }
The return is done at the end of the function. Here is the same program using a recursive function (the first one).

Here is the C code.
#include <stdio.h> // recursive factorial function int fact(int n) { if (n == 0) { return 1; } else { return n * fact(n-1); } } int main() { int f1; printf("Factorials:\n"); for (int i1=0; i1 <= 10; i1++) { f1 = fact(i1); printf("\t%d! is %d\n",i1,f1); } return 0; }
Here is the output of the C code.
Factorials: 0! is 1 1! is 1 2! is 2 3! is 6 4! is 24 5! is 120 6! is 720 7! is 5040 8! is 40320 9! is 362880 10! is 3628800

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.

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.

10 questions omitted (login required)

1 acronyms omitted (login required)