Big-up the Python collections.Counter class massif'

Hey guys, I've known about the Counter class for some time, and did my usual playing around with it when it first came out.

Yesterday I created a player of the Pig Dice Game and needed to create statistics on what strategy had won. I hit on the idea of sending the result in order of the winning strategy of each game played to an instance of the Counter class. A subsequent call of winners.most_common(), (at the end of the prog), collated the statistics I needed.

Today, at work, I was generating a more involved set of stats and I used counter.most_common in a similar way. These calls save me a lot of code which I appreciate, so I'd just like to thank you in a more public fashion.

Cheers people :-)

A permutation journey

Rosetta Code had a new task that had this expression for calculating the determinant of a square matrix (Leibniz's formula):

 

 You can read the wikipedia article to find out more about sigma and sgn or this article which took me step-by-step through to understanding it.

Although the Leibniz formula is inefficient for calculation in general I decided to use it, which meant I needed to create permutations of n items,  σ, and the sign of each permutation

Swapping signs

The sign of a permutation is defined as the parity of the number of swaps between any two items of a permutation needed to generate that permutation from the initial permutation.
So for example, given a starting perm of [0,1,2] the permutation [2,0,1] can be achieved by first swapping the 2 and the 0 to form [2,1,0], then swapping the 1 and 0 to form [2,0,1. That is two swaps in total. The sign of the permutation is given as -1 if an odd number of swaps are used in generating it otherwise as +1 if an even (or no) swaps are needed. (The sign of the permutation will not change even if other swaps, or redundant swaps are used to generate it from the same starting perm).

Pythons itertools.permutations function was of unknown sign, but I picked up on the  Steinhaus–Johnson–Trotter algorithm that generates permutations in such a way that it guarantees that successive permutations only differ by the swapping of two items - this meant that the sign would start as +1 and alternate in sign between successive items.

The Steinhaus–Johnson–Trotter Python program

I decided to create a new Rosetta code task for generating both permutations and their sign with a view for their subsequent use in calculating determinants:

from operator import itemgetter
 
DEBUG = False # like the built-in __debug__
 
def spermutations(n):
    """permutations by swapping. Yields: perm, sign"""
    sign = 1
    p = [[i, 0 if i == 0 else -1] # [num, direction]
         for i in range(n)]
 
    if DEBUG: print ' #', p
    yield tuple(pp[0] for pp in p), sign
 
    while any(pp[1] for pp in p): # moving
        i1, (n1, d1) = max(((i, pp) for i, pp in enumerate(p) if pp[1]),
                           key=itemgetter(1))
        sign *= -1
        if d1 == -1:
            # Swap down
            i2 = i1 - 1
            p[i1], p[i2] = p[i2], p[i1]
            # If this causes the chosen element to reach the First or last
            # position within the permutation, or if the next element in the
            # same direction is larger than the chosen element:
            if i2 == 0 or p[i2 - 1][0] > n1:
                # The direction of the chosen element is set to zero
                p[i2][1] = 0
        elif d1 == 1:
            # Swap up
            i2 = i1 + 1
            p[i1], p[i2] = p[i2], p[i1]
            # If this causes the chosen element to reach the first or Last
            # position within the permutation, or if the next element in the
            # same direction is larger than the chosen element:
            if i2 == n - 1 or p[i2 + 1][0] > n1:
                # The direction of the chosen element is set to zero
                p[i2][1] = 0
        if DEBUG: print ' #', p
        yield tuple(pp[0] for pp in p), sign
 
        for i3, pp in enumerate(p):
            n3, d3 = pp
            if n3 > n1:
                pp[1] = 1 if i3 < i2 else -1
                if DEBUG: print ' # Set Moving'
 
 
if __name__ == '__main__':
    from itertools import permutations
 
    for n in (3, 4):
        print '\nPermutations and sign of %i items' % n
        sp = set()
        for i in spermutations(n):
            sp.add(i[0])
            print('Perm: %r Sign: %2i' % i)
            #if DEBUG: raw_input('?')
        # Test
        p = set(permutations(range(n)))
        assert sp == p, 'Two methods of generating permutations do not agree'

Determinants using Leibniz's formula

I then had all I needed to create the determinant (and permanent) of a matrix code:

from itertools import permutations
from operator import mul
from math import fsum
from spermutations import spermutations
 
def prod(lst):
    return reduce(mul, lst, 1)
 
def perm(a):
    n = len(a); 
    r = range(n); 
    s = list(permutations(r))
    return fsum(prod(a[i][sigma[i]] for i in r) for sigma in s)
 
def det(a):
    n = len(a); 
    r = range(n); 
    s = list(spermutations(n))
    return fsum(sign*prod(a[i][sigma[i]] for i in r) for sigma, sign in s)
 
 
if __name__ == '__main__':
    from pprint import pprint as pp
 
    for a in ( 
            [
             [1, 2], 
             [3, 4]], 
 
            [
             [1, 2, 3, 4],
             [4, 5, 6, 7],
             [7, 8, 9, 10],
             [10, 11, 12, 13]],        
 
            [
             [ 0,  1,  2,  3,  4],
             [ 5,  6,  7,  8,  9],
             [10, 11, 12, 13, 14],
             [15, 16, 17, 18, 19],
             [20, 21, 22, 23, 24]],
        ):
        print('')
        pp(a)
        print('Perm: %s Det: %s' % (perm(a), det(a)))

Sign() of the times

I was still thinking about how to generate the sign of Pythons in-built permutation generator, and a little thought made me think that somewhere there was a sort routine that sorted by swapping two elements. If you count the swaps then you can calculate the sign if the number of swaps is even or odd.

This lead me to Selection Sort. 

def selectionSort(lst):
    for i in range(0,len(lst)-1):
        mn = min(range(i,len(lst)), key=lst.__getitem__)
        lst[i],lst[mn] = lst[mn],lst[i]
    return lst

Unfortunately the sorter does unnecessary swaps so I made a slight modification to create a routine that generated a sign of any permutation of the integers 0..n:

def perm_parity(lst):
    '''\
    Given a permutation of the digits 0..N in order as a list, 
    returns its parity (or sign): +1 for even parity; -1 for odd.
    '''
    parity = 1
    for i in range(0,len(lst)-1):
        if lst[i] != i:
            parity *= -1
            mn = min(range(i,len(lst)), key=lst.__getitem__)
            lst[i],lst[mn] = lst[mn],lst[i]
    return parity    

if __name__ == '__main__':
    from itertools import permutations

    for p in permutations(range(3)):
        l = list(p)
        print "%2i %r" % (perm_parity(l), p)

I published the sign generator on ActiveState as I didn't think it was enough for a Rosetta Code task.

(If you run the code you can see that their is in fact a pattern to the signs generated by successive members Pythons permutations).

Patterns

If you look at a few of the series generated by the Steinhaus–Johnson–Trotter Python program you can see patterns that point to a recursive method of generating the same sequences. I coded that up too.

Serendipity doo dah

A few days later I came across a Stack-exchange question that needed to generate all permutations when there were duplicate items in the initial list. (It goes on to need the permutations in a specific order, but I wasn't thinking of that bit at first).

Of coure I started by generating possible perm then using a set to remove duplicates, but it gets very (very) wasteful, so I started looking around for an algorithm to generate what are sometimes called lexicographically correct permutations. for example the l-perms of [1,1,1,2,2,2] are the twenty terms:

1 1 1 2 2 2
1 1 2 1 2 2
1 2 1 1 2 2
2 1 1 1 2 2
2 1 1 2 1 2
1 2 1 2 1 2
1 1 2 2 1 2
1 2 2 1 1 2
2 1 2 1 1 2
2 2 1 1 1 2
2 2 1 1 2 1
2 1 2 1 2 1
1 2 2 1 2 1
1 1 2 2 2 1
1 2 1 2 2 1
2 1 1 2 2 1
2 1 2 2 1 1
1 2 2 2 1 1
2 2 1 2 1 1
2 2 2 1 1 1

Which is a lot less than 6! = 720 terms of the standard permutation.

I spent an hour playing with my recursive permutation generator until I hit on the idea that if you had to do permutations of 123XX then you could think of each (identical) X as being X0 and X1, and that valid l-perms are the perms when X0 and X1 appear in only one order.

Now the recursive algorithm for perms introduces each item of the initial perm one-by-one. If you restrict each X as it is introduced to never be introduced 'above' and X that is already in the partial perm item that is being expanded, then, in effect, X0 and X1 can never 'cross' and so will stay in the same 'order'.

I made the change and it seems to work for me.

Lexicographic permutation generator in Python

def l_perm(items):
    if not items:
        return [[]]
    else:
        dir = 1
        new_items = []
        this = [items.pop()]
        for item in l_perm(items):
            lenitem = len(item)
            try:
                # Never insert 'this' above any other 'this' in the item 
                maxinsert = item.index(this[0])
            except ValueError:
                maxinsert = lenitem
            if dir == 1:
                # step down
                new_items += [item[:i] + this + item[i:] for i in range(lenitem, -1, -1)
                              if i <= maxinsert]
            else:    
                # step up
                new_items += [item[:i] + this + item[i:] for i in range(lenitem + 1)
                              if i <= maxinsert]
            dir *= -1
        return new_items
 
 
if __name__ == '__main__':
    n = [1, 1, 1, 2, 2, 2]
    print '\nLexicograpic Permutations of %i items: %r' % (len(n), n)
    for i, x in enumerate(l_perm(n)):
        print('%3i %r' % (i, x))

End bit.

I'm tired and I want to go to bed so turning l-perm into a RC task or sticking it on Activestate can wait. I am wondering if their is anyone else interested in this as I just pottered around the less deep bits.


- Paddy.

Cheeky Teens

I have this idea for a new brand called Cheeky Teens. The idea is to sell items carefully designed to be slightly un-hip for teenagers. You know, mobile phones that are branded mo'bile and come with a 1.3 mega pixel main camera. Jeans that cover the waist. Football boots that are as heavy as divers boots of old; (anyone remember 1970's rugby boots)?

The brand would be marketed to exasperated parents looking for that little something for their teens birthday - but with a little twist.

Any more ideas? :-)

Python: Choice of the one obvious way to do it.

I just worked on a new Rosetta Code task on Fibonacci-like sequences where the solution works by giving the initial conditions and being returned something that can then create members of the defined series. You create a series generator factory then use the series generator returned. (The above uses the word generator in its non programming specific sense).

Currently we have three versions of answers to the task in Python:

Python: function returning a function

>>> def fiblike(start):
 addnum = len(start)
 memo = start[:]
 def fibber(n):
  try:
   return memo[n]
  except IndexError:
   ans = sum(fibber(i) for i in range(n-addnum, n))
   memo.append(ans)
   return ans
 return fibber
 
>>> fibo = fiblike([1,1])
>>> [fibo(i) for i in range(10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> lucas = fiblike([2,1])
>>> [lucas(i) for i in range(10)]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
>>> for n, name in zip(range(2,11), 'fibo tribo tetra penta hexa hepta octo nona deca'.split()) :
 fibber = fiblike([1] + [2**i for i in range(n-1)])
 print('n=%2i, %5snacci -> %s ...' % (n, name, ' '.join(str(fibber(i)) for i in range(15))))
 
 
n= 2,  fibonacci -> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...
n= 3, tribonacci -> 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ...
n= 4, tetranacci -> 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ...
n= 5, pentanacci -> 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ...
n= 6,  hexanacci -> 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ...
n= 7, heptanacci -> 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ...
n= 8,  octonacci -> 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ...
n= 9,  nonanacci -> 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ...
n=10,  decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
>>> 

Python: Callable class

>>> class Fiblike():
 def __init__(self, start):
  self.addnum = len(start)
  self.memo = start[:]
 def __call__(self, n):
  try:
   return self.memo[n]
  except IndexError:
   ans = sum(self(i) for i in range(n-self.addnum, n))
   self.memo.append(ans)
   return ans
 
 
>>> fibo = Fiblike([1,1])
>>> [fibo(i) for i in range(10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> lucas = Fiblike([2,1])
>>> [lucas(i) for i in range(10)]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
>>> for n, name in zip(range(2,11), 'fibo tribo tetra penta hexa hepta octo nona deca'.split()) :
 fibber = Fiblike([1] + [2**i for i in range(n-1)])
 print('n=%2i, %5snacci -> %s ...' % (n, name, ' '.join(str(fibber(i)) for i in range(15))))
 
 
n= 2,  fibonacci -> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...
n= 3, tribonacci -> 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ...
n= 4, tetranacci -> 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ...
n= 5, pentanacci -> 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ...
n= 6,  hexanacci -> 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ...
n= 7, heptanacci -> 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ...
n= 8,  octonacci -> 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ...
n= 9,  nonanacci -> 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ...
n=10,  decanacci -> 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
>>> 

Generator

from itertools import islice, cycle
 
def fiblike(tail):
    for x in tail:
        yield x
    for i in cycle(xrange(len(tail))):
        tail[i] = x = sum(tail)
        yield x
 
fibo = fiblike([1, 1])
print list(islice(fibo, 10))
lucas = fiblike([2, 1])
print list(islice(lucas, 10))
 
suffixes = "fibo tribo tetra penta hexa hepta octo nona deca"
for n, name in zip(xrange(2, 11), suffixes.split()):
    fib = fiblike([1] + [2 ** i for i in xrange(n - 1)])
    items = list(islice(fib, 15))
    print "n=%2i, %5snacci -> %s ..." % (n, name, items)

Output:

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
n= 2,  fibonacci -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] ...
n= 3, tribonacci -> [1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136] ...
n= 4, tetranacci -> [1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536] ...
n= 5, pentanacci -> [1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930] ...
n= 6,  hexanacci -> [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617] ...
n= 7, heptanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936] ...
n= 8,  octonacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080] ...
n= 9,  nonanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144] ...
n=10,  decanacci -> [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4088, 8172] ...

Three answers and Zen

So how does the existence of three ways of giving an answer square with that part of the Zen of Python which states:
    There should be one-- and preferably only one --obvious way to do it.

This comes down to a matter of style. Python supports many programming styles, (often called programming paradigms). What example might best fit a situation should depend on the surrounding programming style in use. The function calling a function, callable class, and generator solutions might best fit situations where it is to fit within programs using the procedural, object-oriented and functional styles respectively.

Could N'T care less

I was just enjoying the book "A rising thunder" by David Weber when I came across the phrase "I could care less" (page 448 of the BAEN hardback), meaning in its context: "I could not care less" i.e. there is no lesser degree of care that I could hold. 

I would have thought that even though the phrase may be common usage in the U.S. an author would add the correct phrase. This just jars.

A better candidate selection process

I just read an article that had a good go at explaining why Silicon Valley firms are filled with white middle class males that managed to actually do what it set out to do when it explained why it wanted to take a more reasoned approach. They boil it down to everyone having an in-built bias - not necessarily a good or bad thing, it is just how humans operate. The article then comes up with a very useful experiment:

When selecting from resumes for interview, have the names, age, sex, and origin of the candidates blanked out.

The author found that his resulting selections for interview were a lot different to what he had before.

He goes on to discuss how orchestras changed from being all male affairs to the current mix of genders by them adopting a selection process where candidates played unseen, behind a screen, and where selected based on how well they played.

This got me wondering about the current controversy about Oxbridge admissions. Maybe the universities should adopt similar schemes, candidates should be lead to a separate room, unseen, where voice changers would mask ethnicity and accent, The interview would be audio only and taped, with the selection panel in a separate room. After the interview, the candidate should be given a copy of the tape, and another copy kept for independent review. The idea would be to make the process a better meritocracy rather than the obvious selection of "people like me" that goes on at the moment.

Oh, here's the link to the original article.

Should you worry about a 2x speedup?

Let's take as context an implementation of a task for Rosetta Code - a site set up to compare how different programming languages are used to implement the same task for over five hundred tasks and over four hundred languages.

My short answer would be it depends! You need to:

• Read all of the task description,
• Read some of the solutions in other languages, 
• And maybe skim the tasks talk page

I.e.  ensure you know what the task is asking for and then verify that both solutions solve the task as stated. It can be very easy to misinterpret what the task is asking for, for example, if a task asks for a particular algorithm, do both the examples you are comparing use that algorithm?

As well as comparing two implementations for speed, you should also compare for readability. How well the code reads can have a large impact on how easy the code is to maintain. It has been known for task descriptions to be modified; someone tracking that modification may need to work out if and how code needs to be updated. If an example is overly complex  and/or unidiomatic then it could cause problems.

Time complexity. If one version of code works better when given 'bigger' data then  you need to know more about when that happens - it could be that the cross-over point in terms of speed of execution is never likely to be met. Maybe the size of data needed to reach cross over is unreasonable to expect, or that other mechanisms come into play that mask predicted gains (in other words you might need to verify using that actual bigger data set to account for things like swapping or caching at the OS and hardware level.

How fast does it need to be? Rosetta code doesn't usually mention absolute speed of execution, but if one example takes ten hours and the other takes five then you might want to take that into account. If one example took 0.2 seconds and the other only 0.1 seconds then I guess there is an unwritten expectation that examples "don't take long to run" where long is related to the expectation and patience of the user.

You need to look at the context. In the case of Rosetta code, it may be best to give a solution using a similar algorithm to other examples, or a solution that shows accepted use of the language.

When you make your considered choice, you might want to squirrel away the losing code with notes on why it wasn't used,  - On Rosetta Code we sometimes add more than one solution to a task with comments contrasting the two if they both have merit.

It seems to me that talk about optimising for speed, and speed comparisons tends to dominate on the web over other optimisations, (usually with no extra info on the accuracy of the result. Actually there might be more cases of a revised result that showed not even the first digit of the original answer was right, but more than two digits of precision were shown in the answers)!

Woa - a glitch on Wolfram Mathworld?

I had come across Kaprekar numbers and decided to write a Rosetta Code task around the series. There were issues about the need for extra explanation of why 1 is a member of the series.
I had originally read the wp description and noted that there is a main part to testing if a number is in the series:

 In mathematics, a Kaprekar number for a given base is a non-negative integer, the representation of whose square in that base can be split into two parts that add up to the original number again. For instance, 45 is a Kaprekar number, because 45² = 2025 and 20+25 = 45.

 That is, splitting the ordered digits of the square of the number into two parts that sum to the original number.

Wikipedia then goes on to state that runs of all zeros are not considered positive integers and so 100*100 = 10,000 and 100 + 000 = 100 is disallowed.

What got me was that 1 is considered a member of the series. The only way I could shoe-horn it into the general rule is to allow "splitting" the digits of the square before the first or after the last digit and so producing a number with no digits in it as a partial sum that is allowed and has value zero?!

I widened my references and took a look at the Wolfram Mathworld entry.  Its explanation for the series does not allow for 1 being a member, but shows it as such anyway. It is confused as it describes a series that would exclude numbers 4879 and 5292, i.e. Sloanes A053816; but points to  Sloanes  A006886!

Sloanes A006886 gives another definition for the series:

 Kaprekar numbers: n such that n=q+r and n^2=q*10^m+r, for some m >= 1, q>=0 and 0<=r<10^m, with n != 10^a, a>=1.

 If we try n = 1 then n*n = 1 and there is no m, q, and r that satisfies all the conditions.

I will submit a comment to Mathworld and see what they have to say.

P.S. I could have started this blog entry: "I'm not a mathematician but ..."