Dear all,

I sat down with Frank today and we have (well, Frank has) a new much 
faster algorithm to compute a "crossing number" from a list of subsets.

There are several ways to code and optimize it, and it is necessary to see 
everyone try and make their fastest implementations available to me for 
use in the project.

We will compare times on Friday as we did last week.  It should be fun to 
see how everyone did their implementations.  

Of course, I have an idea for how the fastest implementation will look, 
but I would love to be proven wrong!  As before, free beer goes to the 
winner (Last week Abraham got the beer).

Here is the algorithm to be coded in Perl:

INPUT: Arrays S1,...,Sm of distinct integers from 0 to (n-1)
OUTPUT: An integer which is 0 <==> S1,...,Sm are noncrossing

-------------------------
Crossing Number Algorithm
-------------------------

currMin = Infinity

for each cyclic permutation of the integers 0,...,(n-1) {

  Preprocessing Stage:
    Permute the integers in S1,...,Sm according to this permutation
    Next, For each Si, compute 
    m[i] = min{Si}
    M[i] = max{Si}

  Counting Stage:
    Let CNsum = 0
    for i = 1,...,m {
      for each j in Si { 
          Let currCN = the number of k = 1,...,i-1,i+1,...,m for which
                       m[k] < j < M[k]
         Set CNsum = CNsum + currCN
      }
    }
   If ( CNsum < currMin ) {
	currMin = CNsum
   }
}
return currMin


--------
Example
--------

S1 = 0,3
S2 = 1,4,5
S3 = 2,6

One pass of the algorithm:

0  1  2  3  4  5  6
--------------------
0  1  2  2  1  1  0

Total Sum = 7

(the numbers below are the currCN's for that j)


Please write me with any questions you have about this problem.

-Chris




--------------------
Perl Starter Code:
--------------------

@a = (0,3);
@b = (1,4,5);
@c = (2,6);

@d = (\@a,\@b,\@c);

$n = 7;

#print @a;

print "The Crossing number is: ".cross_number(\@d,$n)."\n";


@a = (0,1,2);
@b = (3,4,5);
@c = (6);

@d = (\@a,\@b,\@c);

$n = 7;

#print @a;

print "The Crossing number is: ".cross_number(\@d,$n)."\n";



############################################################
# crossing number
#
#  INPUT: Arrays S1,...,Sm of distinct integers from 0 to (n-1)
#  OUTPUT: An integer which is 0 <==> S1,...,Sm are noncrossing
#
# -------------------------
# Crossing Number Algorithm
# -------------------------
# 
# currMin = Infinity
# 
# for each cyclic permutation of the integers 0,...,(n-1) {
# 
#   Preprocessing Stage:
#     Permute the integers in S1,...,Sm according to this permutation
#     Next, For each Si, compute 
#     m[i] = min{Si}
#    M[i] = max{Si}
# 
#   Counting Stage:
#     Let CNsum = 0
#     for i = 1,...,m {
#       for each j in Si { 
#           Let currCN = the number of k = 1,...,i-1,i+1,...m for which
#                        m[k] < j < M[k]
#          Set CNsum = CNsum + currCN
#       }
#     }
#    If ( CNsum < currMin ) {
# 	currMin = CNsum
#    }
# }
# return currMin
#
# 
# --------
# Example
# --------
# 
# S1 = 0,3
# S2 = 1,4,5
# S3 = 2,6
# 
# One pass of the algorithm:
# 
# 0  1  2  3  4  5  6
# --------------------
# 0  1  2  2  1  1  0
# 
# Total Sum = 7
# 
#
sub cross_number {
	my ($arrayref,$n) = @_;
	my @arrayofSi = @{$arrayref};

	return 0;	
}