Perverse and Foolish Oft I Strayed [1]
Timothy J Rolfe
Department of Computer Science
Eastern Washington University
319F Computing & Engineering Bldg.
Cheney, WA 99004-2493 USA
Timothy.Rolfe@mail.ewu.edu
http://penguin.ewu.edu/~trolfe/
This is available as a Word documented formatted for
submission to SIGCSE inroads
Abstract
This uses a massively wrong-headed algorithm for sorting to exemplify the use of the backtracking strategy and the branch-and-bound strategy. In addition, brief notes are included on parallel processing approaches: Java threads on multi-core computers and distributed processing through such message passing systems as PVM and MPI.
Keywords
Permutation Generation, Backtracking, Branch and Bound, Algorithm AnalysisCategories and Subject Descriptors G.2.1 Combinatorics [permutations and combinations] I.2.8 Problem Solving, Control Methods, and Search [backtracking] F.2.2 Nonnumerical Algorithms and Problems [sorting and searching] D.1.3 Concurrent Programming [distributed and parallel programming]
The World's Worst Sorting Algorithm
We can view sorting of a list as finding the permutation of elements in which there is no pair out of order. This suggests something to release our true inner geek nature: expressly generate all the permutations until we find one without any out-of-order pairs. This will indeed be an algorithm, since it necessarily will terminate with the correct result . . . eventually. [The competing algorithm is to shuffle the array repeatedly until the sorted condition is met.[2] This is not, however, guaranteed to terminate with the correct result since it is possible that the pseudorandom number generator in use may not find the correct permutation.]
The following Java code segment shows the permSort() method and its helper methods test() and swap().
// Test for no out-of-order pairs
static boolean test(Comparable[] x)
{
for (int k = 1; k < x.length; k++)
if (x[k-1].compareTo(x[k]) > 0)
return false; // out of order
return true; // None bad
}
// Interchange two cells in x
static void swap(Comparable[] x,
int p, int q)
{
Comparable tmp = x[p];
x[p] = x[q]; x[q] = tmp;
}
// Generate and examine permutations
static boolean permSort(Comparable[] x,
int posn)
{
int n = x.length;
if (posn == n) // Full permutation
return test(x);
else
{
Comparable tmp;
int k;
for (k = posn; k < n; k++)
{//Swap next into [posn]
swap (x, k, posn);
// then advance permutation.
if (permSort(x, posn+1))
return true; // Good one!
}
// The above loop right-rotates the
// array segment [posn ... n-1]
// Undoing this is critical so that
// the proper value is in place for
// [posn-1].
tmp = x[posn];
for ( k = posn+1; k < n; k++)
x[k-1] = x[k];
x[n-1] = tmp;
}
return false; // Keep looking.
}
Since the code does exhaustively examine all permutations, it can be accessed
through a header method, discarding the boolean value returned:
static void permSort(Comparable[] x)
{ permSort(x, 0); }
The analysis is obvious: this is an O(n!) algorithm in time, worse even than exponential. The only positive thing that can be said is that it is O(1) in space.
This algorithm does show up on the World-Wide Web. For instance, Adam M. Briska [3] has it in a page with the notation "copyright 2001" — his web page might be copyrightable, but the algorithm itself has been part of computing culture for a long time. A web search on the key “permutation sort” pulls up 396 references, some prior to 2001.
Backtrack to the Rescue
Permutation processing allows us to prune the decision tree very early: as soon as we encounter an out-of-order pair in the current permutation being generated, we can immediately discard all permutations with this front end and back up one level in the decision tree. This is the back-tracking approach [4].
That means that as we permute the values in one position within the vector we know that the vector is sorted up to but not including the present position. Hence we only need to check the current position with respect to the one preceding it. Consequently the boolean method to test for validity needs only to examine one pair.
// Test x[posn] against x[posn-1]
static boolean test(Comparable[] x, int posn)
{ if (posn == 0)
return true; // true if no predecessor
else
return x[posn-1].compareTo(x[posn])<=0;
}
The method backSort() will use this implementation of test() and the swap() shown above, but now when it encounters a full permutation vector, that is immediately the correct solution. In addition, it will advance in generating the permutation only if the present state is valid, taking advantage of the boolean short-circuit evaluation of the Java && operator.
static boolean backSort ( Comparable[] x,
int posn )
{
int n = x.length;
if (posn == n) // Full permutation
return true; // Guaranteed good!
else
{
Comparable tmp;
int k;
for (k = posn; k < n; k++)
{
swap (x, k, posn);
// If good test, advance permutation.
if ( test(x, posn) &&
backSort (x, size, posn+1) )
return true;
}
tmp = x[posn];
for ( k = posn+1; k < n; k++)
x[k-1] = x[k];
x[n-1] = tmp;
}
return false; // Keep looking.
}
Branch and Bound . . . and Bound and Bound
The triumph for our inner geek, however, comes when we apply the branch-and-bound strategy [5]: rather than using recursion we have a list of partial solutions. The list is initialized as the vector in which position zero is being tested. Then, as long as the list is non-empty and we have not found a solution, we expand the next state from that list and generate its subsequent states.
Now, in addition to a potential time complexity of O(n!) we have a matching space complexity that may get to O(n!). In saving the state we need to preserve both the permutation vector and also the position being processed in generating the full permutations. In addition, the list of states can be maintained with several disciplines — stack, queue, or priority queue. The code below preserves the option of having a priority queue, one that preferentially takes longer vectors, and on equal length uses a pure queue discipline. (Java's priority queue is a minheap.)
static class State implements Comparable
{ Comparable[] vect;
int posn,
serial;
static int lastNo = 0;
static long nObj = 0;
public State(Comparable[] vect, int posn)
{
int n = vect.length;
this.posn = posn;
this.vect = new Comparable[n];
System.arraycopy(vect, 0,
this.vect, 0, n);
nObj++;
serial = ++lastNo;
}
public int compareTo(Object o)
{
State rt = (State)o;
// Java has a minheap, so reverse posn
int c1 = rt.posn - this.posn,
c2 = this.serial - rt.serial;
return c1 == 0 ? c2 : c1;
}
}
In the boundSort() method there is no need to regenerate the original permutation vector segment state since each state has its own copy of the permutation vector being processed. Instead of an initial invocation to process subscript zero, the work queue is initialized with the state of the vector being processed in position zero. Instead of the recursive calls, we simply add new states to the work queue. The test() and swap() methods are the same as for backSort().
static void boundSort ( Comparable[] x )
{
// Note: work could be a stack or a queue.
Queue<State> work = new
PriorityQueue<State>();
int n = x.length;
work.add ( new State(x, 0) );
while ( !work.isEmpty() )
{
State test = work.poll();
Comparable[] trial = test.vect;
int posn = test.posn;
if ( posn == n )
// I.e., we have a good permutation
{
System.arraycopy(trial, 0,
x, 0, n);
return;
}
for ( int k = posn; k < n; k++ )
{
// Swap next candidate into [posn]
swap (trial, k, posn);
// then test: on success, add to work
if ( test(trial, posn) )
work.add( new
State(trial,posn+1) );
}
// No need to undo the rotations
}
}
Performance Measurements
The three methods discussed above were run for a range of array lengths to get average times based on a sample size of 1000. The computer used runs the Ubuntu SMP Linux operating system in a configuration that /proc/cpuinfo reports as eight Intel(R) Xeon(TM) CPU 2.80GHz processors. The version of Java and the Java Virtual Machine was 1.5.0_11.
For obvious reasons, the data are plotted with a logarithmic Y axis. Also, because of the speed of the processors, data are shown only in the size range of 8 to 20, and data were collected for permSort() only up to size 10. Both backSort() and boundSort() run massively faster than permSort(), as expected. The overhead of the branch and bound implementation causes it to be noticeably slower than the backtracking implementation.
Parallel Computation — Java Threads
An alternative approach would be to take advantage of parallel processing options. The easiest would be to use Java threads for multiple compute engines on a multi-core computer. For instance, each thread might begin with a different subscript zero entry and then examine the permutations generated by positioning subscripts 1 through (n–1). The thread object can have a static data member by which all of the thread objects can check to see whether another thread has arrived at the solution. Behavior on random data is interesting: aside from the overhead of generating and starting the threads, one may well see extreme speed-up. If the permutation that sorts the data is randomly distributed among all possible permutations, the sequential algorithm must traverse permutations down to that one (possibly with backtracking). The parallel threads, however, may have a thread starting very close to that permutation for rapid detection of a solution. On the other hand, if the solution is close to the end of the first thread's set of permutations, the sequential and threaded solutions (again, aside from overhead) would be about equal.
Parallel Computation — Message Passing
The same exercise can be performed in multiprocessing environments such as those provided by MPI and PVM. The master process sends the initial permutation to the slave processes and receives back status information from them — success/failure, and the sorted vector on success. It can also send a termination message to all slave processes as soon as it receives a success message. Alternatively, rather than starting as many slave processes as the size of the vector (as proposed for the threaded solution), the master process can act as a problem server to the slave processes. Each slave process requests a problem; the master process sends a message with the initial permutation and then updates its own copy for the next permutation to be distributed. It can then send termination messages when a solution is discovered, or when all initial permutations have been sent to slave processes. This approach is attractive in a parallel computing environment of heterogeneous machines. Slower machines simply work on a smaller part of the overall problem than the faster machines.
Summary
If you are faced with a problem that involves evaluation of permutations, and if it is possible to reject whole families of permutations based a front portion of the permutation, you really should use a backtracking or branch and bound approach. Of the two, backtracking is significantly easier to implement and also does not have the massive memory requirements that branch and bound has.
Web Resource
http://penguin.ewu.edu/~trolfe/PermuteSort/index.html. This page provides access to this paper, and also to the Java code given here, embedded in test programs, as well as the benchmark program providing the data for the above graph. Further, it includes code for the briefly mentioned Java threads and distributed processing approaches.
References
/**
* sort Rearrange x so that no element is out of order
*
* @param x Array to be sorted
*/
public static void sort ( Comparable[] x )
{ while ( ! sorted(x) ) shuffle(x); }
/**
* sorted Determine whether the array is sorted.
*
* @param x Array to be tested
* @return false if any element in x is out of order, else true
*/
private static boolean sorted ( Comparable[] x )
{ for ( int j = 1; j < x.length; j++ )
if ( x[j-1].compareTo ( x[j] ) > 0 ) // I.e., comes AFTER
return false;
return true; // NOTHING was out of place
}
// Random number generator used by shuffle
private static java.util.Random gen = new java.util.Random();
/**
* shuffle Randomize position of all array elements
*
* @param x Array to be shuffled
*/
private static void shuffle ( Object[] x )
{ for ( int n = x.length ; n > 1 ; )
{ int k = gen.nextInt(n--); // Note post-decrement
Object temp = x[k];
x[k] = x[n];
x[n] = temp;
}
}
The shuffle algorithm above is discussed in Timothy J Rolfe, "Algorithm Alley:
Randomized Shuffling", Dr. Dobb's Journal, Vol. 25, No. 12 (December 2000),
pp. 113-14. The article is available on-line through http://www.ddj.com/dept/architect/184403979.