Tuesday, October 18, 2011



Testing latex server by watchmath.com.

The are of a triangle is $\frac{1}{2}b*h$.

I thought this was working already! Oh, I have to redo the installation.

January 15, 2012: This is making me sick! this does not work anymore! I changed to mathjax latex server. For instructions, refer to tex.stackexchange.com

Thursday, October 13, 2011

Dennis Ritchie (September 9, 1941 – October 8, 2011: inventor of C programming language

One of my regrets in life is not having to meet in person Dennis Ritichie, the developer of the C programmng language.



I will never forget the time I have to understand pointers (I suspect my instructor did not understand much too!). C is like more a friendlier assembly language in English! C++, Java may be more "in" these days, but they owe their success to the pioneering path blazed by C.

Wednesday, October 12, 2011

Python: Permutations, Combinations, Cartesian Products with Itertools module

Python itertools module has built-in functions for permutations, combinations, cycles and products.
So the Python programmers can focus on building the next killer-apps :) which will dominate the whole world, instead
of reading obtuse treatises, papers, and other publications on algorithms for generating combinatorial objects.

Here we list the combinatorial capabilities of Python (versions 2.6+) in the itertools module.


  • Permutations


    itertools.permutation create a permutation object from an iterable input or string. You can list
    the successive permutations by using object.next() or by creating a list (a bad idea if the size of the object is large!)
    list(object). Here is an example:

    x = itertools.permutation(range(7))
       try:
          while True:
            print x.next()
       except:
          pass
    

    You can also do:

    x = itertools.permutation(range(7))
       for i, e in enumerate(list(x)):
           print i+1, e
    

    Converting to a list give rise to a dangerous situation where you can run out of memory!. but if you know that it can be safely stored,
    by all means use a list conversion.

    Permutations can also accept an extra parameter r so you can generate all permutations of size n of the object taken r at a time.
    The number of elements in such permutations is given by n!/(n-r)!. If r is not specified, then the number of permutations is n!
    which look innocous.(50! is nothing to sneeze at).

  • combinations

  • itertools.combinations creates a combinatorial object. Here ordering does not matter. As an example, the combinations of 6 elements taken 3 at a time can be listed in two groups, as follows:
    import itertools
    
    seq = range(6)
    x = itertools.combinations(seq, 3)
    
    try:
      for i, e in list(enumerate(x)):
         f = [y for y in seq if y not in e]
         print i+1, list(e), f
    except:
       pass
    
    The output of permutations and combinations are tuples for fast execution of the functions, and have to be typecast to a list. Itertools also provide combinations with replacement. The best way to see the difference with the standard combinations is to see them in action from the command line:
    x = combinations_with_replacement([1,2,3,4], 2)
    y = combinations([1,2,3,4], 2)
    
    list(x)
    [(1, 1),
     (1, 2),
     (1, 3),
     (1, 4),
     (2, 2),
     (2, 3),
     (2, 4),
     (3, 3),
     (3, 4),
     (4, 4)]
    
    list(y)
    [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
    
  • Cartesion products


    Itertools has cartesian products! So instead of writing (this from the documentation)

    ((x,y) for x in A for y in B)

    we simply write product(A,B)

    Wait, how about the cartesian product of A with itself?
    you can write product(A,A) or if you want more, product(A,A,A,A). The latter can be written as
    product(A, repeat=4). Python programmers can be lazy as Perl programmers!

  • cycle





  • Not strictly referrring to a mathematical object. Rather it refers to the way an element in an
    iterable is accessed. Instead of stopping at the last element, the access is cycled back to the first element.
    Try this on the command line (not running in a script file)

    x = cycle((1,2,3,4))
    while True:
       print x.next()
    

    You will notice that this loop never terminates, and after the 4 is printed, the next element to be printed is the first element.
    Type Ctrl-C to abort the printing.


Aside from these basic combinatorial objects, Itertools provide now a repeat function! For example, a list of 100
elements with all values equal to 5: [5] * 100 can now be written as itertools.repeat(5, 100). Easier to understand for beginners.


Dont you just love Python?

Hopefully, Python will offer genuine cycle objects (where you can multiply two cycles) and derangements with basic functions such as nPr and nCr. These combinatorial features are solutions waiting for problems and applications!

TO BE CONTINUED.

Saturday, October 1, 2011

Programming Problems: Replace numbers in a list by an increasing sequence.

Consider X = [1, 5, 7, 1, 34]. We want to replace this by X = [1,3,2,1,4].
Consider X = [1000, 500, 700, 5000, 700]. We want to replace this by [3, 1,2,4,2].

Criteria:
1. Use Python. Sorry no java.
2. Fewest lines of code.
3. Elegant, not to use a temporary copy and not using a convoluted BRUTE force method as in the following example, yes I wrote it but that was a temporary solution. I refuse to give a hint, but Python has a powerful discrete math function :)


tempR = X[:]
        for j in range(1, n+1):
            minrank =  min(tempR)
            for k in range(n):
                if X[k] == minrank and k< n+1:
                    X[k] = j
                    tempR[k] = n+1
        return X   
4. Name your function, normalsequence(X). . Here is what I believe a more elegant solution.
def normalsequence(X):
      #ensure that  the ranks are in sequence!
         for i, x in enumerate(sorted(list(set(R[:])))):
             for j, y in enumerate(R):
                 if y == x:
                    R[j] = i+1  
Far more sophisticated (one-liners) for a similar problem is stack overflow: efficient method to calculate the rank vector of a Python list. This solution is also part of the Python code for transforming raw scores to ranks in my other post Python, statistics: Ranking a single array of raw scores