c  go  java  js  lua  py  vbs  rkt  scm  pro  

A constraint logic system is a system of constraints whose solution needs to satisfy those constraints.

A unifier unifies the constraints without contradictions.

A MGU (Most General Unifier) unifies the constraints without contradictions and has a minimal frontier in the lattice of constraints, a LFP (Least Fixed Point) .

If there are multiple solutions, a constraint logic system will attempt to find all MGU constraints.

Constraint processing is a field involved in 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.

The process of enumeration is sometimes called "brute force".

The process of listing every possible alternative, object, thing, etc., is called enumeration.

Brute force enumeration requires looking at all possibilities.

In the case of a combination lock, this is all the possible combinations (permutations).

How many combinations are there on a typical combination lock?

• The numbers on the lock range from 0 to 39, or 40 values.
• There are 3 turns to be made to open the lock.
• Thus, there are 40 choices for the first turn, 40 choices for the second turn, and 40 choices for the third turn.

Thus, the number of combinations for a typical combination lock is 40*40*40 = 64,000.

How long would a brute force attack take? What happens if the last number is known? Note: Order matters, so a combination lock is really a permutation lock. But the generation of the "combinations" does not follow exactly the permutation algorithm (since there is replacement).

To sort something is to arrange that something into order.

To sort a list is to arrange that list so it is in order.

Slowsort is a simple but slow exchange sorting algorithm based on the definition of sorting. That is, take all permutations of the items in the set or multiset to be sorted. At least one such permutation will be in sorted order. Pick one of those permutations to complete the sort.

Obviously, slowsort is not a very machine efficient sorting algorithm.

15 questions omitted (login required)

3 acronyms omitted (login required)