Implementing permutations

Permutations as Coding Question

Preparing some coding questions for next interview for our team I was thinking of a good example to test candidates capabilities to understand how familiar are they with a concept of recursion.

A classic interview example is a an implementation of a power function:

#Function returning n! = 1*2*..*n
def power(n);

or another simple interview favourite:

#Function returning f(n) = f(n-1) + f(n-2)
def fibonacci(n);

To make things a bit more interesting I decided that to find a new and small programming problem which can be implemented using recursion.

I thought permutations are a good example. Specifically a function with following signature:

#Function returning permutations of input list a
def permute(a);

Outline of the Solution

The proposed approach is to use a recursion to implement the function generating all permutations for a given list.

For the purpose of this post let’s focus on a simple list of integers: [1,2,3] (since the implementation in next section is in Python I will stick to Python nomenclature).

On the first level of recursion the algorithm walks through the list and recursively call

def permute(a);

for sublists of the initial list. The consecutive sublists are generated from original list by removing 1st, 2nd up to last element of the original list i.e. for list [1,2,3] the 1st level sublists would be:

[1,2,3]:
        -> [2, 3] (removing ‘1’)

        -> [1,3] (removing ‘2’)

        -> [1,2] (removing ‘3’)

following on 2nd  level we have for 1st level sublists:

[2, 3]: 
       -> [3]

       -> [2]

[1,3]:
      -> [3]

      -> [1]

[1,2]:
      -> [2]

      -> [1] 

starting from [1, 2, 3], the next call to permute() will be with list [2, 3], following by call with arguments [2].

After final level of recursion has been reached the algorithm, will construct the permuted lists by adding the remove sublist element to the front of the sublist returned by next level of permutation for all sublists generated by next level e.g.

[1,2,3]:
        -> [2, 3]: 
                 -> [3] -> [2, 3] -> [1,2,3]
                 -> [2] -> [3, 2] -> [1,3,2]
and so on.

in result the list of generated permutations is as follows (1 * 2 * 3 = 6 permutations):

[1,2,3] 
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1] 

Implementation

Here is an example Python implementation of this algorithm:

#Function returning n! = 1*2*..*n
def permutate(a):
	partial = []
	if len(a) > 1:
		for index in range(0, len(a)):
			prefix = [a[index]]
			print "%s | %s\n" % (a[:index], a[index + 1:])
			sublist = permutate(a[:index] + a[index + 1:])
			for item in sublist:
				partial.append(prefix + item)
	else:
		partial = [a]
	return partial

 

Thread-safety for generic collections in C# 2.0

Recently I had to fix the thread safety issue with a generic dictionary in one of the Spindrift system components. The problem is that no generic collections in C# provides thread-safe methods or at least wrapper classes. My problem was in particular with generic Dictionary class.

MSDN summarizes the threading safety for generic Dictionary in the following paragraph:

''A System.Collections.Generic.Dictionary<,> can support multiple readers concurrently, as long as the collection is not modified. Even so, enumerating through a collection is intrinsically not a thread safe procedure. To guarantee thread safety during enumeration, you can lock the collection during the entire enumeration. To allow the collection to be accessed by multiple threads for reading and writing, you must implement your own synchronization.''

This is a major issue for correct functioning of the multi-threaded system such as Spindrift. This is fixed in version 3.0 of the MS .NET implementation (see System.Collection.Generic Namespace entry on MSDN]) but to be compliant with Mono we decided to keep things up to C# 2.0 standard.

There are three things you can do about it (as outlined by titus here)

• subclass thread usafe class - cons: tedious, also need to reimplement enumerator (see MSDN Dictionary documentation entry as above)
• create utility/helper class doing sychronisation for you - cons: all clients for that generic class have to use that helper class to prevent unclean reads
• creating your own implementation of particular collection class
  

There is actually an another and easy fix. This assumes, however, that you never use enumerators in different threads for the same collection object. You can simply wrap any section of code modifing the collection in your client code using lock.

I initially fixed the problem by adding the critical section around code sections modifying the collection, but of course this means that you need to rememeber to do that for every collection modification you might introduce later. Then I searched through the classes using generic Dictionary in the whole system and this is what I got:

1. DocumentFrequency.cs
2. LinkJustificationFormatter.cs
3. TermFrequency.cs
4. Job.cs
5. Node.cs
6. SimpleXMLJobParser.cs
7. XmlRpcConnector.cs
8. ProcessingState.cs
9. DocumentCache.cs
10. Porter2Test.cs
11. TermFrequencyTest.cs

As much as I would not be concerned much about the test classes system components such as TermFrequency or DocumentCache or Job or Node classes can result in significant issues when multiple threads will be executed in parallel.

I quickly wrote a wrapper for generic Dictionary class but it took much too long to write wrappers for all collections used in the system. The realistic solution is probably to write utility/helper classes for the generic collection classes.