Permutations

This last week I happened to have the necessity of generating all the possible permutations of an array. This seems to be a fairly easy task but many programmers won't come up with a simple solution to this problem very fast. There is at least one intuitive, recursive, solution to this problem, many more complex but *slightly* more efficient, iterative, solutions and no really time-efficient solution. After all, the problem is to generate n! orderings of an array so we, at least, have to visit each one once.

The well-known solution

The most widely spread solution to this problem is the Dijkstra algorithm for generating the next permutation. It is based on the assumption that there is a total order between the elements of the array and the elements of the array are unique (there are no repetitions). If these conditions are met, the algorithm always generates the next permutation in lexicographical order.

The algorithm is very straight forward and goes as follow:

view plainprint?

1. def get_next(a):  
2.     N = len(a)  
3.     i = len(a)-1  
4.   
5.     while a[i-1] >= a[i]:  
6.         i -= 1  
7.   
8.     j = N  
9.   
10.     while a[j-1] <= a[i-1]:  
11.         j -= 1  
12.   
13.     a[i-1], a[j-1] = a[j-1], a[i-1]  
14.   
15.     i += 1  
16.     j = N  
17.   
18.     while i < j:  
19.         a[i-1], a[j-1] = a[j-1], a[i-1]  
20.         i+=1  
21.         j-=1  
22.   
23.     return a  

def get_next(a):
    N = len(a)
    i = len(a)-1

    while a[i-1] >= a[i]:
        i -= 1

    j = N

    while a[j-1] <= a[i-1]:
        j -= 1

    a[i-1], a[j-1] = a[j-1], a[i-1]

    i += 1
    j = N

    while i < j:
        a[i-1], a[j-1] = a[j-1], a[i-1]
        i+=1
        j-=1

    return a

To use this algorithm to generate every possible permutation we just call it n! times:

view plainprint?

1. def dijkstra(a):  
2.     import operator  
3.     fact = reduce(operator.mul, range(1,len(a)+1))  
4.     the_list = [copy(a)]  
5.     for i in range(fact-1):  
6.         a = get_next(a)  
7.         the_list.append(copy(a))  
8.   
9.     return the_list  

def dijkstra(a):
    import operator
    fact = reduce(operator.mul, range(1,len(a)+1))
    the_list = [copy(a)]
    for i in range(fact-1):
        a = get_next(a)
        the_list.append(copy(a))

    return the_list

the only possibly uncommon thing here is line 3 which is a functional-style factorial function.

This works very well for generating the permutations of n (the permutations of the array [0..n-1]) but it won't work for arrays of arbitrary elements. So we explore other options.

The known recursive solution

There's a (not-so-well-)known recursive solution to solving the permutation problem. It is known as the HeapPermute algorithm or Heap's algorithm for permuting an array.
My python implementation of the algorithm goes as follow:

view plainprint?

1. def heap_aux(a, n, the_list):  
2.     if n == 1:  
3.         the_list.append(copy(a))  
4.     else:  
5.         for i in range(n):  
6.             heap_aux(a, n-1, the_list);  
7.   
8.             if n % 2 == 1:  
9.                 a[0], a[n-1] = a[n-1], a[0]  
10.             else:  
11.                 a[i], a[n-1] = a[n-1], a[i]  
12.   
13.   
14. def heap(a):  
15.     the_list = []  
16.     heap_aux(a, len(a), the_list)  
17.     return the_list  

def heap_aux(a, n, the_list):
    if n == 1:
        the_list.append(copy(a))
    else:
        for i in range(n):
            heap_aux(a, n-1, the_list);

            if n % 2 == 1:
                a[0], a[n-1] = a[n-1], a[0]
            else:
                a[i], a[n-1] = a[n-1], a[i]


def heap(a):
    the_list = []
    heap_aux(a, len(a), the_list)
    return the_list

This algorithm works very well and it is very efficient too but it generates the permutations in an order that I find particularly disturbing.
Also it is not as easy to understand as I would like.

Enter my recursive solution
This is probably the most straight forward solution I could come up with. It is a clasical recursive design.
Want to permute an array of n elements? How would you do it if you already had a function to solve the problem for a smaller array?
Simple. Select each possible element of the array to be "the first element of the permutation" and then permute the rest of the array:
A permutation of 1,2,3,4 would be:
1 + permutation_of(2,3,4)
2 + permutation_of(1,3,4)
3 + permutation_of(2,1,4)
4 + permutation_of(2,3,1)

Simple, right?

Let's code it:

view plainprint?

1. for j in range(i, len(a)):  
2.     a[i], a[j] = a[j], a[i]  
3.     permutation(a, i+1, the_list)  
4.     a[i], a[j] = a[j], a[i]  

  for j in range(i, len(a)):
      a[i], a[j] = a[j], a[i]
      permutation(a, i+1, the_list)
      a[i], a[j] = a[j], a[i]

This loop captures the essence of the procedure described above. We have to remember to put the elements back where they were after the recursive call to allow next iteration to work. Not doing so would result in swapping the wrong element in the next iteration.

Puting it all together (and adding a small optimization):

view plainprint?

1. def perm_aux(a, i, the_list):  
2.     if i == len(a):  
3.         the_list.append(copy(a))  
4.     else:  
5.         perm_aux(a, i+1, the_list)  
6.         for j in range(i+1, len(a)):  
7.             a[i], a[j] = a[j], a[i]  
8.             perm_aux(a, i+1, the_list)  
9.             a[i], a[j] = a[j], a[i]  
10.   
11.   
12. def permutate(a):  
13.     the_list = []  
14.     perm_aux(a, 0, the_list)  
15.     return the_list  

def perm_aux(a, i, the_list):
    if i == len(a):
        the_list.append(copy(a))
    else:
        perm_aux(a, i+1, the_list)
        for j in range(i+1, len(a)):
            a[i], a[j] = a[j], a[i]
            perm_aux(a, i+1, the_list)
            a[i], a[j] = a[j], a[i]


def permutate(a):
    the_list = []
    perm_aux(a, 0, the_list)
    return the_list

This algorithm generates the list in a nicer order (though it's not lexicographical). And as its predecessor is quite efficient (taking into account the complexity of the problem).

Performance
Normally recursive algorithms are put down for performance reasons: They keep all local variables stored in the stack while the other recursive calls are made and have to incur in function calling overhead. In the case of these two algorithms the good thing is that the recurtion depth is not proportional to the size of the problem solution but to the size of the array (actually it is exactly as deep as the array's length). Also, if the list variables are passed by reference (this is programming language specific), only the reference to the variable needs to be stored in the stack and there is no overhead of coping the variables on every call.
It will probably never be as efficient as their iterative counterparts but for me readability (with small performance penalties) definitely pays off.

To measure the times I used the following python decorator:

view plainprint?

1. def timing(func):  
2.     def inside(*args):  
3.         t1 = time.time()  
4.         res = func(*args)  
5.         t2 = time.time()  
6.         print '%s took %0.3f ms' % (func.func_name, (t2-t1)*1000.0)  
7.         return res  
8.     return inside  

def timing(func):
    def inside(*args):
        t1 = time.time()
        res = func(*args)
        t2 = time.time()
        print '%s took %0.3f ms' % (func.func_name, (t2-t1)*1000.0)
        return res
    return inside

Given the complexity of the problem, the graph grows rapidly out of scale. So a graph in logarithmic scale is in order



As you can see the algorithms behave very similarly. The largest difference (for an array of size 9) between the fastest (heap) and the slowest (permute) is 0.6 seconds. This of course will grow with the array size, but in a linear instead of exponential manner.


Have another solution to this problem? comment on! =)

sed one-liners

Sed never ceases to amaze me. But I was specially amazed by the fact that "sed is turing complete". Check out this useful sed commands that'll make your life a lot easier!.

Django gets aggregation support!

As for Changeset 9742 Django gets aggregation support. For those of you that don't know, I worked in this project as part of Google Summer of Code and I'm very glad to see this finally coming true!.

I also wanted to thank Russell Keith-Magee for mentoring me throughout the project and working in the code after GSoC was finished, Malcolm Tredinnick for giving amazing code reviews during the whole SoC and the many others that worked in getting this done.

I encourage you to check it out. The documentation is a great start! =)

Emulating Ruby blocks in Python

There are some Ruby features I like a lot. A handful of them are borrowed from other languages (like lisp or perl), but the Matz found a way of making the language a very nice and powerful combination of them. I've been using Ruby lately and got thinking on how could I implement one of Ruby's most beloved features, blocks, in Python (remember, "imitation is the sincerest form of flattery"). As it turns out, it is not all that hard. Here's what I came up with:

But before that...

On Ruby blocks

Blocks in ruby provide a way of creating functions that act on a code block defined later on.
An example of blocks in ruby is the following:

view plainprint?

1. array = [1, 2, 3, 4]  
2. array.each { |n| puts n ** 2 }  
3. 1  
4. 4  
5. 9  
6. 16  

array = [1, 2, 3, 4]
array.each { |n| puts n ** 2 }
1
4
9
16

According to their site: "A block is like an anonymous function or lambda [and] the variable between pipe characters is the parameter for this block". What's missing from this description is that ruby also provides the syntactic sugar to create functions that receive blocks using the "yield" statement. In other words, it is a way of creating closures and attaching them to other methods. Using closures in ruby comes very easily even for people that donsn't know what a closure is. If we were to implement the previous behaviour ourselves we would do something like this:

view plainprint?

1. class Array  
2.     def each2  
3.         for i in self  
4.             yield(i)  
5.         end  
6.     end  
7. end  
8.   
9. array = [1, 2, 3, 4]  
10. array.each2 { |n| puts n ** 2 }  
11. 1  
12. 4  
13. 9  
14. 16  

class Array
    def each2
        for i in self
            yield(i)
        end
    end
end

array = [1, 2, 3, 4]
array.each2 { |n| puts n ** 2 }
1
4
9
16

I won't go into details because there is a lot of documentation on ruby blocks out there.

So, onto Python...

Design
The Python "builtin" that resembles the most to blocks is that of PEP343, the with statement; but I wanted something that immitetad the ruby syntax as much as possible. The with statement is nice, but it doesn't cover all the cases.

So I decided to use a decorator to convert the function that uses the "block" into something that receives the block, inserts it into the namespace, and execute the original function with the block as a corutine.

The idea was something like this:

view plainprint?

1. @receive_block  
2. def simple_iterate():  
3.     for i in [1,2,3]:  
4.         print block()  
5.  
6. @simple_iterate  
7. def _():  
8.     return "a"  

@receive_block
def simple_iterate():
    for i in [1,2,3]:
        print block()

@simple_iterate
def _():
    return "a"

This copies the Ruby syntax except for the receive_block decorator, but I considered it a reasonable sacrifice.
Using "def _()" leaves the function as anonymous and allows you to specify parametrs for the block.

Implementing blocks in Python
So, to implement the syntax I just need to write the receive_block decorator.
The objective of this decorator is to convert the block receiving function, A, into another decorator that receives a function, B, introduces B into A's scope and subsequently calls A.
The key step is to add the block function to the scope. To do this we use Python's builtin types module. It includes the FunctionType method which creates a function object.

view plainprint?

1. types.FunctionType(func.__code__, scope)  

types.FunctionType(func.__code__, scope)

There is more to this method than what we use here, but I won't go into details about the method since we only need the simplest use of it.
Once we know this, the decorator is pretty simple:

view plainprint?

1. import types  
2.   
3. def receive_block(func):  
4.     def decorator(block):  
5.   
6.         # Add block to globals  
7.         scope = func.func_globals #globals()  
8.         scope.update({'block':block})  
9.   
10.         #create the function with the new scope  
11.         new_func = types.FunctionType(func.__code__, scope)  
12.   
13.         return new_func()  
14.   
15.     return decorator  

import types

def receive_block(func):
    def decorator(block):

        # Add block to globals
        scope = func.func_globals #globals()
        scope.update({'block':block})

        #create the function with the new scope
        new_func = types.FunctionType(func.__code__, scope)

        return new_func()

    return decorator

Lets see how it works:

view plainprint?

1. @receive_block  
2. def external():  
3.     for i in [1,2,3]:  
4.         print block()  
5.   
6. print "External"  
7. @external  
8. def _():  
9.     return "a"  

@receive_block
def external():
    for i in [1,2,3]:
        print block()

print "External"
@external
def _():
    return "a"

This will print

view plainprint?

1. External  
2. a  
3. a  
4. a  

External
a
a
a

And if we add a parameter:

view plainprint?

1. @receive_block  
2. def param_external():  
3.      for i in [1,2,3]:  
4.          print block(i)  
5.   
6. print "External with param"  
7. @param_external  
8. def _(i):  
9.     return "a " + unicode(i)  

@receive_block
def param_external():
     for i in [1,2,3]:
         print block(i)

print "External with param"
@param_external
def _(i):
    return "a " + unicode(i)

It, as expected, prints:

view plainprint?

1. External with param  
2. a 1  
3. a 2  
4. a 3  

External with param
a 1
a 2
a 3

But what if we wanted to implement something like ruby's Array class? Lets create an Array class that extends the builtin list type and see what happens.

view plainprint?

1. class Array(list):  
2.     @receive_block  
3.     def each(self):  
4.         for i in self:  
5.             print block(i)  

class Array(list):
    @receive_block
    def each(self):
        for i in self:
            print block(i)

When calling

view plainprint?

1. a = Array([1,2,3,4])  
2.   
3. print "Each Square"  
4. @a.each  
5. def _(x):  
6.     return x**2  

a = Array([1,2,3,4])

print "Each Square"
@a.each
def _(x):
    return x**2

we get the exception:

decorator() takes exactly 1 argument (2 given)

because the instance method takes self as the first argument.
So we modify our initial decorator to work with instance methods:

view plainprint?

1. def receive_block(func):  
2.     def decorator(*args):  
3.         if len(args) == 1:  
4.             block, = args  
5.             instance = None  
6.         elif len(args) == 2:  
7.             instance, block = args  
8.   
9.         # Add block to globals  
10.         scope = func.func_globals #globals()  
11.         scope.update({'block':block})  
12.   
13.         #create the function with the new scope  
14.         new_func = types.FunctionType(func.__code__, scope)  
15.   
16.         if instance:  
17.             return new_func(instance)  
18.         else:  
19.             return new_func()  
20.   
21.     return decorator  

def receive_block(func):
    def decorator(*args):
        if len(args) == 1:
            block, = args
            instance = None
        elif len(args) == 2:
            instance, block = args

        # Add block to globals
        scope = func.func_globals #globals()
        scope.update({'block':block})

        #create the function with the new scope
        new_func = types.FunctionType(func.__code__, scope)

        if instance:
            return new_func(instance)
        else:
            return new_func()

    return decorator

This modification is pretty straight forward. So I won't explain it because it speaks for itself.

Lets write some functions:

view plainprint?

1. class Array(list):  
2. @receive_block  
3. def each(self):  
4.     for i in self:  
5.         print block(i)  
6.  
7. @receive_block  
8. def collect(self):  
9.     for (i, value) in enumerate(self):  
10.         self[i] = block(value)  
11.  
12. @receive_block  
13. def handled(self):  
14.     for i in self:  
15.         try:  
16.             block(i)  
17.         except:  
18.             print "This raised an exception"  

class Array(list):
@receive_block
def each(self):
    for i in self:
        print block(i)

@receive_block
def collect(self):
    for (i, value) in enumerate(self):
        self[i] = block(value)

@receive_block
def handled(self):
    for i in self:
        try:
            block(i)
        except:
            print "This raised an exception"

and pass them some blocks:

view plainprint?

1. a = Array([1,2,3,4])  
2.   
3. print "Each Square"  
4. @a.each  
5. def _(x):  
6.     return x**2  
7.   
8. print "Each"  
9. @a.each  
10. def _(x):  
11.     return x  
12.   
13. print "Collect"  
14. @a.collect  
15. def _(x):  
16.     return x**2  
17.   
18. print a # a is changed  
19.   
20. print "Handled"  
21. @a.handled  
22. def _(x):  
23.     if x != 9:  
24.         raise Exception("this won't work")  
25.     else:  
26.         print "this works"  

a = Array([1,2,3,4])

print "Each Square"
@a.each
def _(x):
    return x**2

print "Each"
@a.each
def _(x):
    return x

print "Collect"
@a.collect
def _(x):
    return x**2

print a # a is changed

print "Handled"
@a.handled
def _(x):
    if x != 9:
        raise Exception("this won't work")
    else:
        print "this works"

We, then, obtain the desired output:

Each Square
1
4
9
16
Each
1
2
3
4
Collect
[1, 4, 9, 16]
Handled
This raised an exception
This raised an exception
this works
This raised an exception

It works. =)

Another interesting way to do this would have been to add the block variable as a free variable of the function and have the code object reference it. In Python, when a closure is created the free variables are stored in an attribute of the function's code object and it's values are stored in the function itself using the cell type. Take this closure as example:

view plainprint?

1. def test():  
2.     a = 10  
3.     b = lambda x: x+2  
4.     def inner():  
5.         print a, b(a)  
6.     return inner  

def test():
    a = 10
    b = lambda x: x+2
    def inner():
        print a, b(a)
    return inner

view plainprint?

1. >>> i = test()  
2. >>> i.func_code.co_freevars  
3. ('a', 'b')  
4. >>> i.func_closure  
5. (< cell int object at 0x802400 >,  
6. < cell function object at 0xf68848 >)  

>>> i = test()
>>> i.func_code.co_freevars
('a', 'b')
>>> i.func_closure
(< cell int object at 0x802400 >,
< cell function object at 0xf68848 >)

Adding the closure to the new function should be easy, since FunctionType accepts a closure keyword argument to do so. Unfortunately, the code's co_freevars attribute is read only:

view plainprint?

1. >>> i.func_code.co_freevars += ('block',)  
2. TypeError: readonly attribute  

>>> i.func_code.co_freevars += ('block',)
TypeError: readonly attribute

If anyone, who knows better than I do, cares to provide an implementation using closures I'd love to hear your solutions.

So this is how we implement Ruby-style blocks in Python using decorators. Hope you enjoyed it.


Disclaimer
This is by no means meant to be used in a production environment. Not even in a semi-serious environment. It is just a hack to demonstrate the how this could be done and it hasn't been tested.


Other notes
* The code for this project is hosted in http://github.com/nicolaslara/blocks/tree/master
* I wanted to implement some of the builtin Ruby functions that use blocks but I didn't have the time. If somebody is up to the task I'd love to see what interesting things could be done with this.
* Also, if somebody is willing to improve the code you are more than welcome.
* Some of the problems of this code:
-It clutters the global namespace.
-The word "block" is introduced as a global reserved word.
* For some reason blogger doesn't let me edit this site's template in 2009, so I couldn't add code syntax highlighting.